
import java.util.*;

// 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
// 可以最终答案取模1e9+7，前提是要保证：所有计算中间结果数据不溢出，
// 否则：所有（可能越界的）中间计算结果都要取模1e9+7

// 栈   
class StackOffer {
    // 剑指Offer 06.从尾到头打印链表

    // 剑指Offer 09.用两个栈实现队列
    // 用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，
    // 分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

    // 方法一：双栈-时间复杂度：对于插入和删除操作，时间复杂度均为 O(1)。
    // 插入不多说，对于删除操作，虽然看起来是 O(n) 的时间复杂度，
    // 精髓：但是仔细考虑下每个元素只会「至多被插入和弹出 stack2 一次」，因此均摊下来每个元素被删除的时间复杂度仍为 O(1)
    // 空间复杂度：O(n)
    class CQueue {
        Deque<Integer> stack1;
        Deque<Integer> stack2;

        public CQueue() {
            stack1 = new LinkedList<Integer>();// 正常入栈顺序
            stack2 = new LinkedList<Integer>();// stack1的反序，即队列的出队顺序
        }

        public void appendTail(int value) {
            stack1.push(value);
        }

        public int deleteHead() {
            // 如果stack2为空
            if (stack2.isEmpty())
                while (!stack1.isEmpty())
                    stack2.push(stack1.pop());

            // 若stack2仍为空
            if (stack2.isEmpty())
                return -1;
            else
                return stack2.pop();

        }
    }

    // 剑指Offer 30.包含min函数的栈（155.hot100有）
    // 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

    // 方法一：最小栈 辅助栈
    class MinStack {
        Deque<Integer> A;
        Deque<Integer> B;// 栈B为辅助栈，为单调栈，单调递减

        public MinStack() {
            A = new LinkedList<>();
            B = new LinkedList<>();
        }

        public void push(int x) {
            A.push(x);
            if (B.isEmpty() || B.peek() >= x)// 栈B为空，或者当前元素比栈顶元素更大
                B.push(x);
        }

        public void pop() {
            // 此题如果用==将会无法通过，Integer的equals重写过，比较的是内部value的值，
            // ==如果在[-128,127]会被cache缓存，超过这个范围则比较的是对象是否相同
            if (A.pop().equals(B.peek()))
                B.pop();
        }

        public int top() {
            return A.peek();
        }

        public int min() {
            return B.peek();
        }
    }

    // 剑指Offer 31.栈的压入、弹出序列（946.hot100无）
    // 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
    // 假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，
    // 但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

    // 方法一：辅助栈 模拟-时间复杂度，空间复杂度：O(n)
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new LinkedList<>();// 模拟栈的进出
        int i = 0;// 出栈顺序的下标
        for (int num : pushed) {
            stack.push(num); // num 入栈
            // 循环判断与出栈
            while (!stack.isEmpty() && stack.peek() == popped[i]) { // 栈非空且栈顶元素为出栈元素
                stack.pop();
                i++;
            }
        }
        // 正常入栈出栈顺序，模拟到最后栈一定为空
        return stack.isEmpty();
    }

    // 剑指Offer 33.二叉搜索树的后序遍历序列
    // 剑指Offer 36.二又搜索树与双向链表

}

// 位运算
class BitOperationOffer {
    // 剑指Offer 15. 二进制中1的个数（191.hot100无 338.hot100类似，求1-n的二进制中1的个数，数组返回）
    // 编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量）。

    // 方法一：循环检查二进制位-时间复杂度：O(k)，其中 k 是 int 型的二进制位数，k=32。
    // 我们需要检查 n 的二进制位的每一位，一共需要检查 32 位。
    // 空间复杂度：O(1)
    public int hammingWeight(int n) {
        int ret = 0;
        for (int i = 0; i < 32; i++)
            if ((n & (1 << i)) != 0)
                ret++;

        return ret;
    }

    // 方法二：位运算优化-时间复杂度：O(logn)，logn<=k，空间复杂度：O(1)
    // Brian Kernighan 算法
    // 原理是：对于任意整数 x，令 x = x & (x − 1)，该运算将 x 的二进制表示的最后一个 1 变成 0
    public int hammingWeight2(int n) {
        int ret = 0;
        while (n != 0) {
            n &= n - 1;
            ret++;
        }
        return ret;
    }

    // Integer.bitCount() 源码 类似归并
    public int hammingWeight3(int n) {
        n = n - ((n >>> 1) & 0x55555555);// 10101010101010101010101010101011 周期是2，每个周期是01
        n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);// 11001100110011001100110011001101 周期是4，每个周期是0011
        n = (n + (n >>> 4)) & 0x0f0f0f0f;// 11110000111100001111000011110001 周期是8，每个是00001111
        n = n + (n >>> 8);
        n = n + (n >>> 16);
        return n & 0x3f;// 0011 1111
    }

    // 行一将i两两分组，每组为这两位中二进制1的个数
    // 按照原理，这行代码也可改写为(i & 0x55555555) + ((i >>> 1) & 0x55555555)
    // 行二将i四四分组，每组为这四位中二进制1的个数
    // 行三将i八八分组，每组为这八位中二进制1的个数
    // 行四将i按十六位分组，每组为这十六位中二进制1的个数，这里也分为了4组，其中2组为垃圾数据
    // 行四将i按三十二位分组，每组为这三十二位中二进制1的个数，这里也分为了4组，其中3组为垃圾数据
    // 行五取出行四运算结果中的有效数据，6位二进制足够表示最大的32位int中的bitCount
    public int hammingWeight33(int n) {
        n = (n & 0x55555555) + ((n >> 1) & 0x55555555);// 0101 0101 0101 0101 ... 周期是2，每个周期是 01
        n = (n & 0x33333333) + ((n >> 2) & 0x33333333);// 0011 0011 0011 0011 ... 周期是4，每个周期是 0011
        n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);// 0000 1111 0000 1111 ... 周期是8，每个是 0000 1111
        n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);// 0000 0000 1111 1111 ...
        n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
        return n;
    }

    // 剑指Offer 53 - II.0~ n-1中缺失的数字

    // 剑指Offer 56 - I.数组中数字出现的次数（136.hot100有类似，只出现一次的数字，异或运算的性质：a^a=0 a^0=a）
    // 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。
    // 要求时间复杂度是O(n)，空间复杂度是O(1)。

    // 方法一：分组异或-时间复杂度：O(n)，空间复杂度：O(1)
    // 拓展为找2个只出现一次的数，利用异或性质分组（保证同一个数分到同一个组，目标两数在不同组即可，位运算与0比较做分组！）
    // 考虑异或操作的性质：对于两个操作数的每一位，相同结果为 0，不同结果为 1。
    // 那么在计算过程中，成对出现的数字的所有位会两两抵消为 0，最终得到的结果就是那个出现了一次的数字。
    // 那么这一方法如何扩展到找出两个出现一次的数字呢？
    // 如果我们可以把所有数字分成两组，使得：
    // 两个只出现一次的数字在不同的组中；
    // 相同的数字会被分到相同的组中。

    // xi=0示ai和bi相等。假如我们任选一个不为0的xi，按照第i位给原来的序列分组，
    // 如果该位为0就分到第一组，否则就分到第二组，这样就能满足以上两个条件，为什么呢?
    // 首先，两个相同的数字的对应位都是相同的，所以一个被分到了某一组，另一个必然被分到这一组，所以满足了条件2。
    // 这个方法在xi= 1的时候a和b不被分在同一组，因为xi=1示ai和bi不等，根据这个方法的定义
    // 「如果该位为0就分到第一组，否则就分到第二组」可以知道它们被分进了两组，所以满足了条件1。
    // 在实际操作的过程中，我们拿到序列的异或和x之后，对于这个「位」可以任取的，只要它满足xi= 1。
    // 但是为了方便，这里的代码选取的是「不为0的最低位」，当然你也可以选择其他不为0的位置。

    public int[] singleNumbers(int[] nums) {
        int ret = 0;
        for (int n : nums)
            ret ^= n;
        // 得到两个出现一次的数字的异或值

        int div = 1;// 靠这一位来分组
        while ((div & ret) == 0)// 得到不为0的最低位
            div <<= 1;

        int a = 0, b = 0;// 两组
        for (int n : nums) {
            if ((div & n) != 0)
                a ^= n;
            else
                b ^= n;
        }
        return new int[] { a, b };
    }

    // 剑指Offer 56 - II.数组中数字出现的次数 II
    // 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

    // 解题思路：
    // 如下图所示，考虑数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是 3 的倍数。
    // 因此，统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字。

    // 方法一：有限状态自动机-时间复杂度：O(n)，空间复杂度：O(1)
    // 0→1→2→0→⋯
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;// 状态一、状态二
        for (int num : nums) {
            // 00 11=0 10 01=1 if 0(1)=0 1(0)=ones
            ones = ones ^ num & ~twos;
            // if two == 0:
            // one = one ^ n
            // if two == 1:
            // one = 0

            twos = twos ^ num & ~ones;
        }
        return ones;
    }

    // 方法二：遍历统计（位运算）-时间复杂度：O(n)，空间复杂度：O(1)
    // 统计每一位上是否为1，直接右移该数，实际上遍历每个数的每一位不需要32次判断（右移为0则没有1了，提前结束）
    public int singleNumber2(int[] nums) {
        int[] counts = new int[32];
        for (int num : nums) {// 遍历每个数
            for (int j = 0; j < 32; j++) {// 遍历每个数的每一位 下标31最高位 下标0最低位
                counts[j] += num & 1;// 效率比判断一下num & 1的结果，再进行++ 要快很多！
                num >>= 1;
            }
        }
        int res = 0, m = 3;
        for (int i = 0; i < 32; i++) {// 遍历统计数组的每一位
            res <<= 1;
            res |= counts[31 - i] % m;// 取余只可能是0或者1
        }
        return res;
    }

    // 方法二：（自己写的）遍历统计（位运算）-时间复杂度：O(n)，空间复杂度：O(1)
    public int singleNumber22(int[] nums) {
        int bitCount[] = new int[32];
        for (int num : nums) {
            int index = 0;
            while (num != 0) {
                bitCount[index] += (num & 1);// 不要判断一下num & 1的结果，再进行++
                index++;
                num >>= 1;
            }
        }
        int res = 0;
        int count = 1;
        for (int i = 0; i < 32; i++) {
            if (bitCount[i] % 3 == 1)
                res = res | count;
            count <<= 1;
        }
        return res;
    }

    // 剑指Offer 64.求1+2+... +n

    // 剑指Offer 65.不用加减乘除做加法-时间复杂度：O(k)，k<32，空间复杂度：O(1)
    // 写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
    public int add(int a, int b) {
        // 第一次与b作和后，后续都是与进位作和
        while (b != 0) { // 当进位全为 0 时跳出
            int c = (a & b) << 1; // c = 进位 11 = 1 01 01 = 10
            a ^= b; // a = 非进位和 00 11 = 0， 01 10 = 1
            b = c; // b = 进位
        }
        return a;
    }

}

// 树
class TreeOffer {
    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }

    // 剑指Offer 07.重建二叉树（105.hot100有）
    // 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
    // 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
    // 1.递归-时间复杂度、空间复杂度：O(n)
    // 无重复元素，则可用哈希表
    // 递归时，需要传入前序、中序的左右边界
    Map<Integer, Integer> indexMap;

    TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，值——→索引，以便快速定位中序遍历中对应根节点的索引值，而前序遍历的根节点一定是区间内第一个节点
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++)
            indexMap.put(inorder[i], i);
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    // ========================前序遍历========中序遍历=====前序遍历索引的左区间，右区间============中序遍历索引的左区间，右区间
    TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left,
            int inorder_right) {
        // 前序遍历的形式:[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]，即根节点总是前序遍历中的第一个节点
        // 中序遍历的形式:[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
        // 前序遍历的左区间用来确定根节点，右区间用来确定是否有子树，没有则提前返回null
        // 中序遍历的根节点由前序遍历的左区间确定，左区间确定左子树的节点数目
        if (preorder_left > preorder_right)// 单独使用前序遍历，或中序遍历的区间范围来判断都可行
            return null;

        int preorder_root = preorder_left;// 前序遍历中的第一个节点就是根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);// 在中序遍历中定位根节点
        TreeNode root = new TreeNode(preorder[preorder_root]); // 先把根节点建立出来
        int size_left_subtree = inorder_root - inorder_left;// 得到左子树中的节点数目
        // 递归地构造左右子树，并连接到根节点
        // 先序遍历左子树边界[左边界+1, 左边界+size_left_subtree]，中序遍历左子树边界[左边界, 根节点定位-1]
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left,
                inorder_root - 1);
        // 先序遍历右子树边界「左边界+1+左子树节点数目, 右边界」，中序遍历右子树边界「根节点定位+1, 右边界」
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right,
                inorder_root + 1, inorder_right);
        return root;
    }

    // 2.迭代-时间复杂度、空间复杂度：O(n)
    // 对于前序遍历中的任意两个连续节点 u 和 v，根据前序遍历的流程，可知 u 和 v 只有两种可能的关系：
    // 1. v 是 u 的左孩子。这是因为在遍历到 u 之后，下一个遍历的节点就是 u 的左孩子，即 v
    // 2. u 没有左孩子，并且 v 是 u 的某个祖先节点（或者 u 本身）的右孩子。如果 u 没有左孩子，那么下一个遍历的节点就是 u 的右孩子
    // 如果 u 没有右孩子，我们就会向上回溯，直到遇到第一个有右孩子（且 u 不在它的右孩子的子树中）的节点 u_a，那么 v 就是 u_a 的右孩子
    TreeNode buildTree2(int[] preorder, int[] inorder) {
        if (preorder == null) // 空树提前返回null
            return null;
        TreeNode root = new TreeNode(preorder[0]);
        // 用一个栈 stack 来维护「当前节点的所有还没有考虑过右孩子的祖先节点」，栈顶就是当前节点。也就是说，只有在栈中的节点才可能连接一个新的右孩子
        // 有点类似于中序遍历的迭代中的栈
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);// 根节点入栈
        int inorderIndex = 0;// 指向中序遍历的某个位置，当前节点不断往左走达到的最终节点
        for (int i = 1; i < preorder.length; i++) {
            int preorderVal = preorder[i];// 例子中的节点v，根节点是节点u
            TreeNode node = stack.peek();// 根节点出栈
            if (node.val != inorder[inorderIndex]) {// 情况1. 节点v是u的左孩子
                // 若inorderIndex已是不断往左走达到的最终节点（节点u没有左孩子），则进入情况2.
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);// 没有考虑过右孩子的节点通通入栈
            } else {// 情况2. u 没有左孩子，向上回溯
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);// 没有考虑过右孩子的节点通通入栈
            }
        }
        return root;
    }

    // 剑指Offer 26.树的子结构
    // 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)（ps. B还是可能为空，坑逼）
    // B是A的子结构， 即 A中有出现和B相同的结构和节点值。

    // 方法一：递归（先序遍历）-时间复杂度 O(MN)，空间复杂度 O(M)
    // 其中 M,N 分别为树 A 和 树 B 的节点数量
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 逻辑运算符的短路性质
        // if(A != null && B != null)
        // (recur(A, B)
        // 分别从节点A B判断B是不是A的子结构

        // recur(A, B)满足直接返回true，不再切换树A的节点进行判断
        // recur(A, B)false就开始执行||后的isSubStructure，遍历树A的后续节点进行判断
        // ||后的只要有一个为true就返回true

        // isSubStructure(A.left, B) || isSubStructure(A.right, B))
        // 先左后右遍历树A的节点，重复以上判断
        // return (A != null && B != null)
        // && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));

        if (A != null && B != null)
            if (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B))
                return true;

        return false;// A B有一个为null就返回false 不进行recur(A, B)

    }

    // 从节点A B判断B是不是A的子结构
    boolean recur(TreeNode A, TreeNode B) {
        if (B == null)
            return true;
        if (A == null || A.val != B.val)
            return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }

    // 剑指Offer 27.二叉树的镜像（226.hot100有）

    // 1.递归DFS（先序）-时间复杂度、空间复杂度：O(n)
    // 请完成一个函数，输入一个二叉树，该函数输出它的镜像。
    public TreeNode mirrorTree(TreeNode root) {
        if (root != null) {
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;

            mirrorTree(root.left);
            mirrorTree(root.right);
        }
        return root;
    }

    // 2.迭代BFS-时间复杂度、空间复杂度：O(n)
    public TreeNode mirrorTree2(TreeNode root) {
        if (root == null)
            return null;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                TreeNode temp = node.left;
                node.left = node.right;
                node.right = temp;
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }

        return root;
    }

    // 剑指Offer 28.对称的二叉树（101.hot100有）
    // 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

    // 1.递归DFS-时间复杂度O(n)
    public boolean isSymmetric(TreeNode root) {
        // 头节点的特殊处理，少一遍重复
        if (root == null)
            return true;

        return check(root.left, root.right);

    }

    boolean check(TreeNode left, TreeNode right) {
        if (left == null && right == null)
            return true;

        if (left != null && right != null)
            if (left.val == right.val)
                return check(left.left, right.right) && check(left.right, right.left);

        return false;
    }

    // （101.hot100有）
    // 2.迭代BFS（队列）-时间复杂度O(n)
    // 3.迭代DFS（栈）-时间复杂度O(n)

    // 剑指Offer 32-1.从上到下打印二叉树
    // 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

    // 方法一：bfs 辅助队列-时间复杂度、空间复杂度：O(n)
    public int[] levelOrder(TreeNode root) {
        if (root == null)
            return new int[] {};

        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            res.add(node.val);
            if (node.left != null)
                queue.offer(node.left);
            if (node.right != null)
                queue.offer(node.right);
        }
        int[] resArray = new int[res.size()];
        for (int i = 0; i < resArray.length; i++)
            resArray[i] = res.get(i);

        return resArray;
    }

    // 剑指Offer 32 - II.从上到下打印二叉树（102.hot100有）
    // 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

    // 方法一：bfs 辅助队列 多元素拓展-时间复杂度、空间复杂度：O(n)
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null)
            return ans;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int level = queue.size();
            List<Integer> res = new ArrayList<>(level);

            for (int i = 0; i < level; i++) {
                TreeNode node = queue.poll();
                res.add(node.val);
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
            ans.add(res);
        }
        return ans;
    }

    // 剑指Offer 32 - III.从上到下打印二叉树
    // 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，
    // 第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

    // 方法一：层序遍历 bfs + 双端队列-时间复杂度、空间复杂度：O(n)
    public List<List<Integer>> levelOrder3(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null)
            return ans;

        Deque<TreeNode> queue = new LinkedList<>();
        queue.offerLast(root);

        while (!queue.isEmpty()) {
            int level = queue.size();
            List<Integer> res = new ArrayList<>(level);

            if (ans.size() % 2 == 1)
                for (int i = 0; i < level; i++) {
                    TreeNode node = queue.pollLast();// 队尾出队
                    res.add(node.val);
                    if (node.right != null)
                        queue.offerFirst(node.right);// 从右子树开始，队头入队
                    if (node.left != null)
                        queue.offerFirst(node.left);

                }
            else
                for (int i = 0; i < level; i++) {
                    TreeNode node = queue.pollFirst();// 队头出队
                    res.add(node.val);
                    if (node.left != null)
                        queue.offerLast(node.left);// 从左子树开始，队尾入队
                    if (node.right != null)
                        queue.offerLast(node.right);
                }

            ans.add(res);
        }
        return ans;
    }

    // 方法二：层序遍历 + 倒序
    public List<List<Integer>> levelOrder4(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if (root != null)
            queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }

            if (res.size() % 2 == 1)
                Collections.reverse(tmp);// 倒序
            res.add(tmp);
        }
        return res;
    }

    // 剑指Offer 33.二叉搜索树的后序遍历序列（判断，而不是重建）
    // 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。
    // 如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
    // 后序遍历定义： [ 左子树 | 右子树 | 根节点 ] ，即遍历顺序为 “左、右、根” 。
    // 二叉搜索树定义： 左子树中所有节点的值 << 根节点的值；右子树中所有节点的值 >> 根节点的值；其左、右子树也分别为二叉搜索树。

    // 方法一：递归分治-时间复杂度 O(N^2)，空间复杂度 O(N)
    // 根据二叉搜索树的定义，可以通过递归，判断所有子树的 正确性 （即其后序遍历是否满足二叉搜索树的定义） ，
    // 若所有子树都正确，则此序列为二叉搜索树的后序遍历。
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }

    // 子树区间[i, j] 根节点必为j
    boolean recur(int[] postorder, int i, int j) {
        // 没有继续划分的必要了
        if (i >= j)
            return true;

        // 划分左右子树
        int p = i;
        while (postorder[p] < postorder[j])
            p++;
        int m = p;// [i, m-1]为左子树，[m, j-1]为右子树（正确情况下）
        while (postorder[p] > postorder[j])// 在右子树区间内继续遍历，最后在根节点处跳出（正确情况下）
            p++;
        // （正确情况下：左右子树大小正常）（左子树）（右子树）
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }

    // 方法二：辅助单调栈（单调递减）（执行效率甚至更低）-时间复杂度 O(N)，空间复杂度 O(N)
    // 后序遍历倒序： [ 根节点 | 右子树 | 左子树 ] 。
    // 类似 先序遍历的镜像 ，即先序遍历为 “根、左、右” 的顺序，而后序遍历的倒序为 “根、右、左” 顺序。
    // 根据以上特点，考虑借助单调栈实现:
    // 1.借助一个单调栈stack存储值递增的节点;
    // 2.每当遇到值递减的节点ri，则通过出栈来更新节点ri的父节点root;（最后出栈的为根节点）
    // 3.每轮判断ri和root的值关系:
    // 1.若ri > root则说明不满足二叉搜索树定义，直接返回false。
    // 2.若ri < root则说明满足二叉搜索树定义，则继续遍历。（当前节点位于根节点的左子树下）
    public boolean verifyPostorder2(int[] postorder) {
        Deque<Integer> stack = new LinkedList<>();// 递增
        int root = Integer.MAX_VALUE;
        stack.push(Integer.MIN_VALUE);

        for (int i = postorder.length - 1; i >= 0; i--) {// 后序遍历倒序
            int curr = postorder[i];
            if (curr > root)
                return false;
            while (stack.peek() > curr)// 保持单调栈的递增特性
                root = stack.pop();// 更新root
            stack.push(curr);// 每个节点必入栈
        }
        return true;
    }

    // 剑指Offer 34.二叉树中和为某一值的路径（113.路径总和II 437.hot100有类似，路径总和III）
    // 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从「根节点」到「叶子节点」路径总和等于给定目标和的路径。
    // 叶子节点 是指没有子节点的节点。

    // 方法一：深度优先搜索 dfs-时间复杂度：O(N^2)，空间复杂度：O(N)
    List<List<Integer>> ret = new LinkedList<List<Integer>>();// 最终答案
    Deque<Integer> path = new LinkedList<Integer>();// 从根节点 root开始的一条路径

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root, target);
        return ret;
    }

    public void dfs(TreeNode root, int target) {
        if (root == null)
            return;

        path.offerLast(root.val);// 当前节点加入路径
        target -= root.val;
        if (root.left == null && root.right == null && target == 0) // 找到一个解，复制一份list加入最终答案
            ret.add(new LinkedList<Integer>(path));

        dfs(root.left, target);// 左子树
        dfs(root.right, target);// 右子树
        path.pollLast();// 注意结束时去除末尾元素，还原。target是局部变量，不用还原
    }

    // 方法二：广度优先搜索 bfs-时间复杂度：O(N^2)，空间复杂度：O(N)
    // 我们也可以采用广度优先搜索的方式，遍历这棵树。
    // 当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径。
    // 为了节省空间，我们使用哈希表记录树中的每一个节点的父节点。
    // 每次找到一个满足条件的节点，我们就从该节点出发不断向父节点迭代，即可还原出从根节点到当前节点的路径。
    List<List<Integer>> ret2 = new LinkedList<List<Integer>>();
    Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();

    public List<List<Integer>> pathSum2(TreeNode root, int target) {
        if (root == null)
            return ret2;

        // 辅助队列维护遍历节点，对应和
        Queue<TreeNode> queueNode = new LinkedList<TreeNode>();
        Queue<Integer> queueSum = new LinkedList<Integer>();
        queueNode.offer(root);
        queueSum.offer(0);

        while (!queueNode.isEmpty()) {
            // 成对出队
            TreeNode node = queueNode.poll();
            int rec = queueSum.poll() + node.val;

            if (node.left == null && node.right == null) {
                if (rec == target) // 一个解
                    getPath(node);

            } else {
                if (node.left != null) {
                    map.put(node.left, node);
                    // 成对入队
                    queueNode.offer(node.left);
                    queueSum.offer(rec);
                }
                if (node.right != null) {
                    map.put(node.right, node);
                    // 成对入队
                    queueNode.offer(node.right);
                    queueSum.offer(rec);
                }
            }
        }

        return ret2;
    }

    // 每次找到一个满足条件的节点，我们就从该节点出发不断向父节点迭代，即可还原出从根节点到当前节点的路径。
    public void getPath(TreeNode node) {
        List<Integer> temp = new LinkedList<Integer>();
        while (node != null) {
            temp.add(node.val);
            node = map.get(node);
        }
        Collections.reverse(temp);
        ret2.add(new LinkedList<Integer>(temp));
    }

    // 剑指Offer 36.二又搜索树与双向链表（426.hot100无）

    // 方法一：中序遍历 dfs-时间复杂度，空间复杂度 O(N)
    // 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
    // 本文解法基于性质：二叉搜索树的中序遍历为 递增序列 。
    // 将 二叉搜索树 转换成一个 “排序的循环双向链表” ，其中包含三个要素：
    // 排序链表： 节点应从小到大排序，因此应使用 中序遍历 “从小到大”访问树的节点。
    // 双向链表： 在构建相邻节点的引用关系时，
    // 设前驱节点 pre 和当前节点 cur ，不仅应构建 pre.right = cur ，也应构建 cur.left = pre 。
    // 循环链表： 设链表头节点 head 和尾节点 tail ，则应构建 head.left = tail 和 tail.right = head 。
    Node pre, head;

    public Node treeToDoublyList(Node root) {
        if (root == null)
            return null;
        dfs(root);// 递归结束后，pre为尾节点，head为头节点
        head.left = pre;
        pre.right = head;
        return head;
    }

    void dfs(Node cur) {
        if (cur == null)
            return;
        dfs(cur.left);// 左子树

        if (pre != null)
            pre.right = cur;// 前驱指向当前
        else
            head = cur;// pre为空时，找到头节点
        cur.left = pre;// 当前指向前驱
        pre = cur;// 移动

        dfs(cur.right);// 右子树
    }

    // 方法一：
    Node dummyHead = new Node(-1);
    boolean findHead = false;
    Node prev;

    public Node treeToDoublyList11(Node root) {
        if (root == null)
            return null;
        myDFS(root);
        prev.right = dummyHead.right;
        dummyHead.right.left = prev;
        return dummyHead.right;
    }

    private void myDFS(Node root) {
        if (root == null)
            return;

        myDFS(root.left);

        if (!findHead) {
            findHead = true;
            dummyHead.right = root;
            prev = root;
        } else {
            prev.right = root;
            root.left = prev;
            prev = root;
        }

        myDFS(root.right);

    }

    // 方法二：迭代 栈-时间复杂度，空间复杂度 O(N)
    public Node treeToDoublyList2(Node root) {
        if (root == null)
            return null;
        Node pre = null;
        Node head = null;
        Node cur = root;
        Deque<Node> stk = new LinkedList<>();
        while (cur != null || !stk.isEmpty()) {// 节点为空指针且栈为空时才跳出
            while (cur != null) {
                stk.push(cur);
                cur = cur.left;
            } // 跳出循环时，cur必为null
            cur = stk.pop();

            if (pre != null)
                pre.right = cur;// 前驱指向当前
            else
                head = cur;// pre为空时，找到头节点
            cur.left = pre;// 当前指向前驱
            pre = cur;// 移动

            cur = cur.right;// cur可能为空
        }
        // 循环结束后，pre为尾节点，head为头节点
        head.left = pre;
        pre.right = head;
        return head;
    }

    // 剑指Offer 37.序列化二叉树（297.hot100有）
    // 请实现两个函数，分别用来序列化和反序列化二叉树。
    // 你需要设计一个算法来实现二叉树的序列化与反序列化。
    // 这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
    // 提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。
    // 你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
    // Your Codec object will be instantiated and called as such:
    // Codec ser = new Codec();
    // Codec deser = new Codec();
    // TreeNode ans = deser.deserialize(ser.serialize(root));

    // 方法一：DFS（先序遍历）-时间复杂度、空间复杂度：O(n)
    // 后序遍历应该也可以，中序遍历应该不能
    // 先序遍历，String用,隔开，null用None表示，再按先序遍历反序列化
    // 含有所有null的先序遍历，是可以还原出树的结构的
    // String类型是引用数据类型，但是因为有字符串常量池，做参数是值的复制
    // StringBuilder是引用数据类型，做参数是传递地址
    String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder("");
        rserialize(root, sb);
        return new String(sb);
    }

    void rserialize(TreeNode root, StringBuilder str) {
        if (root == null)
            str.append("None,");
        else {
            str.append(String.valueOf(root.val) + ",");// 先序遍历
            rserialize(root.left, str);
            rserialize(root.right, str);
        }

    }

    TreeNode deserialize(String data) {
        String[] dataArray = data.split(",");
        Queue<String> dataList = new LinkedList<>(Arrays.asList(dataArray));// 数组转List，如果就要使用数组，需要传入index指向当前节点位置
        return rdeserialize(dataList);
    }

    TreeNode rdeserialize(Queue<String> dataList) {
        String curString = dataList.poll();// 不用判断队列是否为空，一定能完美还原二叉树
        if ("None".equals(curString))
            return null;

        // 按先序遍历反序列化
        TreeNode root = new TreeNode(Integer.parseInt(curString));
        root.left = rdeserialize(dataList);
        root.right = rdeserialize(dataList);
        return root;
    }

    // 方法二：括号表示编码（中序遍历）+ 递归下降解码
    // 时间复杂度、空间复杂度：O(n) 为什么时间缩短10倍
    // 也可以这样表示一颗二叉树：
    // 如果当前的树为空，则表示为 X
    // 如果当前的树不为空，则表示为 (左子树序列化之后的结果)当前节点val(右子树序列化之后的结果)
    // 根据这样的定义，很好写出序列化的过程，「后序遍历」这颗二叉树即可，像方法1那样从左至右序列化不行
    // 那如何反序列化呢？根据定义，我们可以推导出这样的巴科斯范式（BNF）：
    // T -> (T) num (T) | X
    // 它的意义是：用 T 代表一棵树序列化之后的结果，| 表示 T 的构成为 (T) num (T) 或者 X
    // | 左边是对 T的递归定义，右边规定了递归终止的边界条件

    String serialize2(TreeNode root) {
        return rserialize2(root);
    }

    String rserialize2(TreeNode root) {
        if (root == null)
            return "X";

        return "(" + rserialize2(root.left) + ")" + root.val + "(" + rserialize2(root.right) + ")";
    }

    TreeNode deserialize2(String data) {
        int[] ptr = { 0 };// 为了不创建类的成员变量，（基本数据类型传入数据的复制，引用数据类型传入地址），用包装类也不行
        return parse(data, ptr);
    }

    TreeNode parse(String data, int[] ptr) {
        if (data.charAt(ptr[0]) == 'X') {
            ++ptr[0];
            return null;
        }
        TreeNode cur = new TreeNode(0);
        ++ptr[0]; // 跳过左括号
        cur.left = parse(data, ptr);// 左子树
        ++ptr[0]; // 跳过右括号

        cur.val = parseInt(data, ptr);// 当前节点值

        ++ptr[0]; // 跳过左括号
        cur.right = parse(data, ptr);// 右子树
        ++ptr[0]; // 跳过右括号
        return cur;
    }

    int parseInt(String data, int[] ptr) {
        int x = 0, sgn = 1;// 节点值有正负，-1000 <= Node.val <= 1000
        if (!Character.isDigit(data.charAt(ptr[0]))) {// 数字第一位是-
            sgn = -1;
            ++ptr[0];
        }
        while (Character.isDigit(data.charAt(ptr[0])))
            x = x * 10 + data.charAt(ptr[0]++) - '0';

        return x * sgn;
    }

    // 剑指Offer 54.二叉搜索树的第k大节点
    // 给定一棵二叉搜索树，请找出其中第k大的节点。

    // 方法一：dfs 中序遍历（逆序）-时间复杂度、空间复杂度：O(n)
    int res, k;

    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }

    void dfs(TreeNode root) {
        if (root == null)
            return;

        dfs(root.right);// 右子树

        if (--k == 0) {
            res = root.val;
            return;// 提前返回，不再往后遍历
        }
        dfs(root.left);// 左子树
    }

    // 方法二：迭代-时间复杂度：O(n)，空间复杂度：O(1)
    public int kthLargest2(TreeNode root, int k) {
        Deque<TreeNode> stk = new LinkedList<>();
        while (stk != null || root != null) {
            while (root != null) {
                stk.push(root);
                root = root.right;
            }
            root = stk.pop();
            if (--k == 0)
                return root.val;

            root = root.left;
        }
        return -1;
    }

    // 剑指Offer 55- I.二叉树的深度（104.hot100有）
    // 给定一个二叉树，找出其最大深度。
    // 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
    // 说明: 叶子节点是指没有子节点的节点。

    // 方法一：深度优先搜索 dfs-时间复杂度：O(n)，空间复杂度：O(height)
    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;

        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    // 方法二：广度优先搜索 bfs-时间复杂度，空间复杂度：O(n)
    public int maxDepth2(TreeNode root) {
        if (root == null)
            return 0;

        Queue<TreeNode> queue = new LinkedList<TreeNode>();// 辅助队列
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();// 每次遍历同一层的节点
            while (size > 0) {
                TreeNode node = queue.poll();
                if (node.left != null)
                    queue.offer(node.left);

                if (node.right != null)
                    queue.offer(node.right);

                size--;
            }
            ans++;
        }
        return ans;
    }

    // 剑指Offer 55-II.平衡二叉树（110.hot100无）
    // 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

    // 方法一：自底向上的递归-时间复杂度，空间复杂度：O(n)
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0; // 只有可能是 -1 或 正数
    }

    public int height(TreeNode root) {
        if (root == null)
            return 0;

        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1)
            return -1;// 后续会提前返回
        else
            return Math.max(leftHeight, rightHeight) + 1;
    }

    // 方法一：（自己写的）递归-时间复杂度，空间复杂度：O(n)
    boolean flag;

    public boolean isBalanced11(TreeNode root) {
        dfs55(root);
        return !flag;
    }

    private int dfs55(TreeNode root) {
        if (root == null || flag)
            return 0;

        int leftDepth = dfs55(root.left);
        int rightDepth = dfs55(root.right);
        if (Math.abs(leftDepth - rightDepth) > 1)
            flag = true;

        return Math.max(leftDepth, rightDepth) + 1;

    }

    // 剑指Offer 68-I.二叉搜索树的最近公共祖先（235.hot100无，236.普通二叉树的最近公共祖先）
    // （主要考察利用到二叉搜索树的性质）
    // 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
    // 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，
    // 最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

    // 方法一：两次遍历-时间复杂度，空间复杂度：O(n)
    // 根据二叉搜索树的性质，找到从根节点到p q节点的路径，然后从根节点开始，找到最后一个公共祖先节点，即最近公共祖先

    // 方法二：一次遍历-时间复杂度，空间复杂度：O(n)
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while (true) {
            // 当前节点的值大于 p 和 q 的值，说明 p 和 q 应该在当前节点的左子树，因此将当前节点移动到它的左子节点；
            if (p.val < ancestor.val && q.val < ancestor.val)
                ancestor = ancestor.left;
            // 当前节点的值小于 p 和 q 的值，说明 p 和 q 应该在当前节点的右子树，因此将当前节点移动到它的右子节点；
            else if (p.val > ancestor.val && q.val > ancestor.val)//
                ancestor = ancestor.right;
            // 当前节点的值不满足上述两条要求，那么说明当前节点就是「分岔点」。
            // 此时，p 和 q 要么在当前节点的不同的子树中，要么其中一个就是当前节点。
            else
                return ancestor;
        }
    }

    // 剑指Offer 68- II.二叉树的最近公共祖先（236.hot100有）

    // 方法一：递归DFS（后序遍历）-时间复杂度，空间复杂度-O(n)
    // 递归遍历整棵二叉树，定义 fx 表示 x 节点的子树中是否包含 p 节点或 q 节点，如果包含为 true，否则为 false
    // 那么符合条件的最近公共祖先 x 一定满足如下条件：
    // (flson && frson) ||  ((x = p || x = q) && (flson || frson))
    // flson && frson一定符合
    // (x = p || x = q) && (flson || frson)同时满足也符合，即父节点是p或q且另一个在其左或右子树下
    TreeNode ans = null;

    boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return false;
        boolean lson = dfs(root.left, p, q);// p q 是否在左子树下
        boolean rson = dfs(root.right, p, q);// p q 是否在右子树下
        if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson)))
            ans = root;

        return lson || rson || (root.val == p.val || root.val == q.val);// p q是否在该节点下，或该节点就是p q
    }

    TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        this.dfs(root, p, q);
        return ans;
    }

    // 方法二：存储父节点-时间复杂度，空间复杂度-O(n)
    // 不是顺序二叉树，不能简单通过序号来判断是否是父节点
    Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();// 键值对，key为节点val，value为该节点的父节点
    Set<Integer> visited = new HashSet<Integer>();// 所有节点p的祖先节点（包括p自身）

    TreeNode lowestCommonAncestor4(TreeNode root, TreeNode p, TreeNode q) {
        dfsAllNodes(root);
        while (p != null) {
            visited.add(p.val);// p的所有父节点，包括p节点自己
            p = parent.get(p.val);// p的父节点
        }
        while (q != null) {
            if (visited.contains(q.val))// 找到共同的祖先节点
                return q;
            q = parent.get(q.val);
        }
        return null;
    }

    void dfsAllNodes(TreeNode root) {
        if (root.left != null) {
            parent.put(root.left.val, root);
            dfsAllNodes(root.left);
        }
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfsAllNodes(root.right);
        }
    }

    // 方法二：（自己写的）存储父节点-时间复杂度，空间复杂度-O(n)
    // 值传递踩了大坑，以后不要犯这种低级错误
    List<TreeNode> temp;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pFathers = new ArrayList<>();
        List<TreeNode> qFathers = new ArrayList<>();
        temp = new ArrayList<>();
        dfs(root, p, pFathers);
        temp = new ArrayList<>();
        dfs(root, q, qFathers);

        TreeNode res = root;
        int size = Math.min(pFathers.size(), qFathers.size());
        for (int i = 0; i < size; i++) {
            if (pFathers.get(i) == qFathers.get(i))
                res = pFathers.get(i);
            else
                break;
        }
        return res;
    }

    private void dfs(TreeNode root, TreeNode target, List<TreeNode> fathers) {
        if (root == null)
            return;
        temp.add(root);
        if (root == target) {
            fathers.addAll(temp);// 值传递踩了大坑，以后不要犯这种低级错误
            return;
        }

        dfs(root.left, target, fathers);
        dfs(root.right, target, fathers);
        temp.remove(temp.size() - 1);
    }
}

// 设计
class DesignOffer {
    // 剑指Offer 09.用两个栈实现队列
    // 剑指Offer 30.包含min函数的栈
    // 剑指Offer 37.序列化二叉树

    // 剑指Offer 41.数据流中的中位数（295.hot100无）
    // 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
    // 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
    // 例如，
    // [2,3,4] 的中位数是 3
    // [2,3] 的中位数是 (2 + 3) / 2 = 2.5
    // 设计一个支持以下两种操作的数据结构：
    // void addNum(int num) - 从数据流中添加一个整数到数据结构中。
    // double findMedian() - 返回目前所有元素的中位数。
    // 进阶:
    // 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
    // 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

    // 方法一：优先队列-时间复杂度：addNum: O(logn)，findMedian: O(1)。空间复杂度：O(n)
    // 思路和算法
    // 我们用两个优先队列 queMax（小根堆）和 queMin（大根堆）分别记录大于中位数的数和小于等于中位数的数。
    // 即：两个堆中元素的数量关系要满足：queMin = [queMax, queMax + 1]
    // 当累计添加的数的数量为奇数时，queMin 中的数的数量比 queMax 多一个，此时中位数为 queMin 的队头。
    // 当累计添加的数的数量为偶数时，两个优先队列中的数的数量相同，此时中位数为它们的队头的平均值。

    // 当我们尝试添加一个数 num 到数据结构中，我们需要分情况讨论：
    // 1. num≤max{queMin}
    // num 小于等于中位数，我们需要将该数添加到 queMin 中。
    // 新的中位数将小于等于原来的中位数，因此我们可能需要将 queMin 中最大的数移动到 queMax 中。
    // 2. num>max{queMin}
    // 此时 num 大于中位数，我们需要将该数添加到 queMax 中。
    // 新的中位数将大于等于原来的中位数，因此我们可能需要将 queMax 中最小的数移动到 queMin 中。
    // 特别地，当累计添加的数的数量为 0 时，我们将 num 添加到 queMin 中。
    class MedianFinder {
        PriorityQueue<Integer> queMin;
        PriorityQueue<Integer> queMax;

        public MedianFinder() {
            queMin = new PriorityQueue<Integer>((a, b) -> (b - a));// 大根堆
            queMax = new PriorityQueue<Integer>((a, b) -> (a - b));// 小根堆
        }

        // 两个堆中元素的数量关系要满足：queMin = [queMax, queMax + 1]
        public void addNum(int num) {
            if (queMin.isEmpty() || num <= queMin.peek()) {
                queMin.offer(num);
                if (queMin.size() > queMax.size() + 1)// queMin中元素太多了，匀一个给queMax
                    queMax.offer(queMin.poll());
            } else {
                queMax.offer(num);
                if (queMin.size() < queMax.size())// queMin中元素太少了，匀一个给queMin
                    queMin.offer(queMax.poll());
            }
        }

        public double findMedian() {
            if (queMin.size() > queMax.size())// 奇数个元素
                return queMin.peek();
            return (queMin.peek() + queMax.peek()) / 2.0;// 偶数个元素
        }
    }

    // 方法二：（自己写的）维护有序序列（列表 + 二分查找）-时间复杂度：addNum: O(n)，findMedian: O(1)。空间复杂度：O(n)
    // 效率并不比方法一差...
    class MedianFinder2 {
        List<Integer> list;

        public MedianFinder2() {
            list = new ArrayList<>();
        }

        public void addNum(int num) {
            if (list.size() == 0)
                list.add(num);
            else {// 插入至有序序列
                int index = Collections.binarySearch(list, num);
                if (index >= 0)
                    list.add(index, num);
                else
                    index = -index - 1;
                list.add(index, num);
            }
        }

        public double findMedian() {
            int n = list.size();
            if (n % 2 == 0)
                return (list.get(n / 2 - 1) + list.get(n / 2)) / 2.0;
            else
                return list.get(n / 2);
        }
    }

    // 剑指Offer 59 - I.队列的最大值

}

// 递归
class RecursionOffer {
    // 剑指Offer 06.从尾到头打印链表
    // 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

    // 方法一：递归-时间复杂度：O(n)，空间复杂度：O(n)
    // 实际写有坑，List.toArray不能将List<Integer> 转换为 int[]，不能用List（还用递归有点亏）
    public int[] reversePrint(ListNode head) {

        ListNode node = head;
        int length = 0;
        while (node != null) {// 获取链表长度
            node = node.next;
            length++;
        }
        int[] res = new int[length];
        recursion(head, res, 0, length);
        return res;
    }

    public void recursion(ListNode node, int[] res, int index, int length) {
        if (node != null) {
            recursion(node.next, res, index + 1, length);
            res[length - index - 1] = node.val;
        }
    }

    // 方法二：栈-时间复杂度：O(n)，空间复杂度：O(n)
    public int[] reversePrint2(ListNode head) {
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode temp = head;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        int size = stack.size();
        int[] print = new int[size];
        for (int i = 0; i < size; i++)
            print[i] = stack.pop().val;
        return print;
    }

    // Collections.reverse(ans); 自己写的-时间复杂度：O(n)，空间复杂度：O(n)
    public int[] reversePrint3(ListNode head) {
        List<Integer> ans = new ArrayList<>();
        while (head != null) {
            ans.add(head.val);
            head = head.next;
        }
        Collections.reverse(ans);
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++)
            res[i] = ans.get(i);
        return res;
    }

    // 剑指Offer 16.数值的整数次方（50.hot100无）
    // 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n）。不得使用库函数，同时不需要考虑大数问题。

    // 用例挖坑，计算2^(-2147483648)，而java int范围是-2^31 <= n <= 2^31-1，转为正数会越界

    // 方法一：快速幂 + 迭代-时间复杂度：O(logn)，空间复杂度：O(1)
    public double myPow(double x, int n) {
        if (x == 0)
            return 0.0;
        if (n == 0)
            return 1.0;
        boolean isNegtive = n < 0;
        int one = isNegtive ? -1 : 1;
        double res = 1.0;
        while (n != 0) {
            if (n % 2 == one)
                res *= x;

            x = multiply(x);
            n /= 2;
        }

        return isNegtive ? 1 / res : res;
    }

    double multiply(double x) {
        return x * x;
    }

    // 方法一：快速幂 + 迭代（自己写的）-时间复杂度：O(logn)，空间复杂度：O(1)
    public double myPow11(double x, int n) {
        if (x == 1.0)
            return 1.0;

        if (n == 0)
            return 1.0;
        else if (n > 0)
            return pow(x, n);
        else
            return 1.0 / pow(x, -n);

    }

    private double pow(double x, int n) {
        double ans = 1;
        double xs = x;
        while (n != 0) {
            if ((n & 1) == 1)
                ans = ans * xs;

            xs = xs * xs;
            n = n / 2;
        }
        return ans;
    }

    // 方法二：快速幂 + 递归-时间复杂度：O(logn)，空间复杂度：O(logn)
    public double myPow2(double x, int n) {
        if (x == 0)
            return 0.0;
        if (n == 0)
            return 1.0;
        boolean isNegtive = n < 0;
        int one = isNegtive ? -1 : 1;

        return isNegtive ? 1 / myPowRec(x, n, one) : myPowRec(x, n, one);
    }

    double myPowRec(double x, int n, int one) {
        if (n == 0)
            return 1.0;

        if (n % 2 == one)
            return x * myPowRec(x * x, n / 2, one);
        else
            return myPowRec(x * x, n / 2, one);
    }

    // 剑指Offer 19.正则表达式匹配

    // 剑指Offer 24.反转链表（206.hot100有）
    // 方法一：递归-时间复杂度：O(n)，空间复杂度：O(n)
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null)
            return head;

        ListNode newHead = reverseList(head.next);
        head.next.next = head;

        // 当前节点指向null 后续会被更改，直到重新回到原头节点，防止新链表末尾（原链表头）成环
        head.next = null;

        return newHead;
    }

    // 方法二：迭代-时间复杂度：O(n)，空间复杂度：O(1)
    public ListNode reverseList2(ListNode head) {

        ListNode prev = null;
        ListNode curr = head;
        ListNode next;
        while (curr != null) {// 由curr跳出，需要避免next空指针
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;

        }
        return prev;
    }

    // 剑指Offer 25.合并两个排序的链表（21.hot100有）
    // 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

    // 方法一：迭代-时间复杂度：O(n+m)，空间复杂度：O(1)
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead; // 合并链表的当前节点
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }

        // 拼接尾巴
        if (l1 == null)
            cur.next = l2;
        if (l2 == null)
            cur.next = l1;
        return dummyHead.next;
    }

    // 方法二：递归-时间复杂度、空间复杂度：O(m+n)
    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        if (l1 == null)// 只要有一个链表结束，则整个合并结束
            return l2;
        else if (l2 == null)
            return l1;
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);// 先传入原l1.next参数，再改变l1.next指向
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    // 剑指Offer 33.二叉搜索树的后序遍历序列

    // 剑指Offer 43.1~n整数中1 出现的次数

    // 剑指Offer 62.圆圈中最后剩下的数字（约瑟夫环）
    // 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里「删除第m个」数字（删除后从下一个数字开始计数）。
    // 求出这个圆圈里剩下的最后一个数字。
    // 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，
    // 因此最后剩下的数字是3。

    // 方法一：数学 + 递归-时间复杂度、空间复杂度：O(n)
    public int lastRemaining(int n, int m) {
        return f(n, m);
    }

    // n 个成环数中依次删除第m个数，返回值为最终留下的元素的序号
    // 返回值 ( m + x ) % n
    // m 固定不变， e.g. m=3, ( m + x ) % n，答案范围：0 - n-1
    // x 为 n-1时函数的返回值（表示相对位置），即被删掉数字的相对索引值（相对位置）
    // n = 1，返回0， 3
    // n = 2，返回1， 1 3
    // n = 3，返回1， 1 3 4
    // n = 4，返回0 3 4 0 1
    // n = 5，返回3， 0 1 2 3 4
    // 相对顺序是一样的，则 0 1 1 0 3 是对应n的答案
    // 0
    // 0 1
    // 0 1 2
    // 0 1 2 3
    // 0 1 2 3 4

    public int f(int n, int m) {
        if (n == 1)
            return 0;

        int x = f(n - 1, m);
        return (m + x) % n;
    }

    // 方法二：数学 + 迭代（动态规划）-时间复杂度：O(n)，空间复杂度：O(1)
    public int lastRemaining2(int n, int m) {
        int f = 0;
        for (int i = 2; i != n + 1; ++i)
            f = (m + f) % i;

        return f;
    }

    // 剑指Offer 64.求1+2+... +n
    // 求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
    // 限制：
    // 1 <= n <= 10000

    // 方法一：递归-时间复杂度：O(n)，空间复杂度：O(n)
    // boolean = (if里的判断)&&(if下的语句，随便写成一个判断即可);
    // 通常实现递归的时候我们都会利用条件判断语句来决定递归的出口，
    // 但由于题目的限制我们不能使用条件判断语句，那么我们是否能使用别的办法来确定递归出口呢？
    // 答案就是逻辑运算符的短路性质。
    // 以逻辑运算符 && 为例，对于 A && B 这个表达式，如果 A 表达式返回 False ，
    // 那么 A && B 已经确定为 False ，此时不会去执行表达式 B。
    // 同理，对于逻辑运算符 ||， 对于 A || B 这个表达式，如果 A 表达式返回 True ，
    // 那么 A || B 已经确定为 True ，此时不会去执行表达式 B。
    // 利用这一特性，我们可以将判断是否为递归的出口看作 A && B 表达式中的 A 部分，递归的主体函数看作 B 部分。
    // 如果不是递归出口，则返回 True，并继续执行表达式 B 的部分，否则递归结束。
    public int sumNums(int n) {
        @SuppressWarnings("unused")
        boolean flag = (n > 0) && ((n += sumNums(n - 1)) > 0);
        return n;
    }

    // 方法二：快速乘-时间复杂度：O(logn)，空间复杂度：O(1)
    // 考虑 A 和 B 两数相乘的时候我们如何利用加法和位运算来模拟，其实就是将 B 二进制展开，
    // 如果 B 的二进制表示下第 i 位为 1，那么这一位对最后结果的贡献就是 A∗(1<<i) ，
    // 即 A<<i。我们遍历 B 二进制展开下的每一位，将所有贡献累加起来就是最后的答案，这个方法也被称作「俄罗斯农民乘法」

    // 回到本题，由等差数列求和公式我们可以知道1+2+... +n=(1+n)n/2
    // 对于除以 2 我们可以用右移操作符来模拟，那么等式变成了 n(n+1)>>1，
    // 剩下不符合题目要求的部分即为 n(n+1)，根据上文提及的快速乘，
    // 我们可以将两个数相乘用加法和位运算来模拟，但是可以看到上面的 C++ 实现里我们还是需要循环语句，
    // 有没有办法去掉这个循环语句呢？答案是有的，那就是自己手动展开，
    // 因为题目数据范围 n 为 [1,10000]，所以 n 二进制展开最多不会超过 14 位，
    // 我们手动展开 14 层代替循环即可
    public int sumNums2(int n) {
        int ans = 0, A = n, B = n + 1;
        @SuppressWarnings("unused")
        boolean flag;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        return ans >> 1;
    }

}

// 队列
class QueueOffer {

    // 剑指Offer 09.用两个栈实现队列
    // 剑指Offer 50.第一个只出现一次的字符

    // 剑指Offer 59 - I.滑动窗口的最大值（239.hot100有）
    // 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
    // 窗口大小k可能过大，直接使用max()复杂度O(nk)过高！

    // 方法一：优先队列-时间复杂度：O(nlogn)，将一个元素放入优先队列的时间复杂度为 O(logn)
    // （该题只需要求窗口内最大值，并不关系整个窗口内的排序，使用堆一定程度上做了无用功，同理二叉排序树）
    // 空间复杂度：O(n)
    // 在优先队列中存储二元组 (num,index)，表示元素 num 在数组中的下标为 index

    // 方法二：单调队列（双端队列）-时间复杂度：O(n)，空间复杂度：O(k)
    // 单调队列存放索引值，按元素大小严格单调递减
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0)
            return new int[] {};

        // 单调队列
        Deque<Integer> deque = new LinkedList<Integer>();
        // 初始时，我们将数组 nums 的前 k 个元素放入单调队列中
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()])// 队列非空且当前入队元素比队尾元素大
                deque.pollLast();// 队尾元素的索引出队
            deque.offerLast(i);// 插入至队尾
        }

        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()];// 队头即最大值
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()])
                deque.pollLast();
            deque.offerLast(i);

            while (deque.peekFirst() <= i - k) // 队头元素已不在窗口内（要循环判断，直到堆顶元素在窗口内）
                deque.pollFirst();

            ans[i - k + 1] = nums[deque.peekFirst()];// 队头即最大值
        }
        return ans;
    }

    // 方法三：分块 + 预处理-时空复杂度：O(n)
    // 我们可以将数组 nums 从左到右按照 k 个一组进行分组，最后一组中元素的数量可能会不足 k 个。
    // 那么 nums[i] 到 nums[i+k−1] 会跨越两个分组，占有第一个分组的后缀以及第二个分组的前缀。
    // 如果我们能够预处理出每个分组中的前缀最大值以及后缀最大值，同样可以在 O(1) 的时间得到答案。
    // 这种方法与稀疏表（Sparse Table）非常类似

    // 剑指Offer 59 - II.队列的最大值
    // 请定义一个队列并实现函数 max_value 得到队列里的最大值，
    // 要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
    // 若队列为空，pop_front 和 max_value 需要返回 -1

    // 方法一：暴力
    // 思路
    // 直接实现一个普通的队列，查询最大值时遍历计算。

    // 方法二：维护一个单调递减的双端队列（类比59 - I 和 Offer30.最小栈，利用数据结构栈和队列的特性）
    // 时间复杂度：O(1)，空间复杂度：O(n)
    class MaxQueue {
        Queue<Integer> q;
        Deque<Integer> d;

        public MaxQueue() {
            q = new LinkedList<Integer>();
            d = new LinkedList<Integer>();
        }

        public int max_value() {
            if (d.isEmpty())
                return -1;
            return d.peekFirst();
        }

        public void push_back(int value) {
            while (!d.isEmpty() && d.peekLast() <= value) // （要循环判断，直到队头元素在窗口内）
                d.pollLast();
            d.offerLast(value);
            q.offer(value);
        }

        public int pop_front() {
            if (q.isEmpty())
                return -1;
            int ans = q.poll();// 不直接使用两个Integer比较，超过127会比较地址是否相等
            if (ans == d.peekFirst())
                d.pollFirst();
            return ans;
        }
    }

    // 方法二：（自己写的）单调队列
    class MaxQueue22 {

        Deque<Integer> queue;
        Deque<Integer> monoqueue;

        public MaxQueue22() {
            queue = new LinkedList<>();
            monoqueue = new LinkedList<>();
        }

        public int max_value() {
            if (queue.isEmpty())
                return -1;
            return monoqueue.peekFirst();
        }

        public void push_back(int value) {
            queue.offerLast(value);
            while (!monoqueue.isEmpty() && monoqueue.peekLast() < value)
                monoqueue.pollLast();

            monoqueue.offerLast(value);
        }

        public int pop_front() {
            if (queue.isEmpty())
                return -1;

            if (queue.peekFirst().equals(monoqueue.peekFirst()))// 最好直接用equals()比较两个Integer
                monoqueue.pollFirst();

            return queue.pollFirst();
        }
    }
}

// 数组
class ArrayOffer {
    // 剑指Offer 03.数组中重复的数字
    // 剑指Offer 04.二维数组中的查找
    // 剑指Offer 07.重建二叉树
    // 剑指Offer 11.旋转数组的最小数字

    // 剑指Offer 12.矩阵中的路径（79.hot100有）
    // 方法一：回溯-时间复杂度：O(MN 3^L)（实际远小于此），空间复杂度：O(MN)
    char[][] myBoard;
    String myWord;
    // 标记是否被访问过
    boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        int h = board.length, w = board[0].length;
        myBoard = board;
        myWord = word;
        visited = new boolean[h][w];
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
                if (check(i, j, 0))
                    return true;

        return false;
    }

    // 当前坐标i j，当前递归到的字符位置k
    public boolean check(int i, int j, int k) {
        if (myBoard[i][j] != myWord.charAt(k))
            return false;
        else if (k == myWord.length() - 1)
            return true;

        visited[i][j] = true;
        // 上下左右四个方向（实际最多三个有可能）
        int[][] directions = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

        for (int[] dir : directions) {
            // 下一步
            int newi = i + dir[0], newj = j + dir[1];
            // 判断是否越界
            if (newi >= 0 && newi < myBoard.length && newj >= 0 && newj < myBoard[0].length)
                // 判断是否访问过
                if (!visited[newi][newj])
                    if (check(newi, newj, k + 1))
                        return true;

        }
        // 结束递归时还原
        visited[i][j] = false;
        return false;
    }

    // 剑指Offer 17.打印从1到最大的n位数
    // 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

    // 大数越界问题： 当 n 较大时，endend 会超出 int32 整型的取值范围，超出取值范围的数字无法正常存储。
    // 但由于本题要求返回 int 类型数组，相当于默认所有数字都在 int32 整型取值范围内，因此不考虑大数越界问题。
    public int[] printNumbers(int n) {
        int end = (int) Math.pow(10, n) - 1;
        int[] res = new int[end];
        for (int i = 0; i < end; i++)
            res[i] = i + 1;
        return res;
    }

    // 大数打印解法-时间复杂度 O(10^n)，空间复杂度 O(10^n)
    // 实际上，本题的主要考点是大数越界情况下的打印。需要解决以下三个问题：
    // 1. 表示大数的变量类型：
    // 无论是 short / int / long ... 任意变量类型，数字的取值范围都是有限的。因此，大数的表示应用字符串 String 类型。
    // 2. 生成数字的字符串集：
    // 使用 int 类型时，每轮可通过 +1 生成下个数字，而此方法无法应用至 String 类型。
    // 并且， String 类型的数字的进位操作效率较低，例如 "9999" 至 "10000" 需要从个位到千位循环判断，进位 4 次。
    // 观察可知，生成的列表实际上是 n 位 0 - 9 的 全排列 ，因此可避开进位操作，通过递归生成数字的 String 列表。
    // 3. 递归生成全排列：
    // 基于分治算法的思想，先固定高位，向低位递归，当个位已被固定时，添加数字的字符串。
    // 例如当 n = 2 时（数字范围 1 - 99 ），固定十位为 0 - 9 ，按顺序依次开启递归，固定个位 0 - 9 ，终止递归并添加数字字符串。

    // 各数字字符串被逗号隔开，共同组成长字符串。
    StringBuilder res;
    // 各位中9的数量，字符串的左边界，位数
    int nine = 0, start, n;
    // 每个数的字符数组
    char[] num, loop = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };

    public String printNumbers2(int n) {
        this.n = n;
        res = new StringBuilder();
        num = new char[n];
        start = n - 1;// 字符串的左边界
        dfs(0);// 从高位开始（下标0）
        res.deleteCharAt(res.length() - 1);// 删除末尾逗号
        return res.toString();
    }

    void dfs(int x) {
        if (x == n) {// n位上都填充了字符，转为字符串加入res，由于是dfs，一定是从0, 1, 2,...开始的（去除）
            String s = String.valueOf(num).substring(start);
            if (!s.equals("0"))
                res.append(s + ",");// 逗号隔开
            if (n - start == nine)// 所有位上都为9，左边界左移
                start--;
            return;
        }
        for (char i : loop) {
            if (i == '9')
                nine++;
            num[x] = i;
            dfs(x + 1);
        }
        nine--;// 9的个数减一，还原
    }

    // 剑指Offer 21.调整数组顺序使奇数位于偶数前面

    // 剑指Offer 29.顺时针打印矩阵（54.hot100无）
    // 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

    // 方法一：按层模拟-时间复杂度：O(mn)，空间复杂度：O(1)
    public int[] spiralOrder(int[][] matrix) {
        if (matrix.length == 0)
            return new int[0];

        int[] res = new int[matrix.length * matrix[0].length];
        // 上边界，下边界，左边界，右边界
        int u = 0, d = matrix.length - 1, l = 0, r = matrix[0].length - 1;// 四个边界
        int idx = 0;

        while (true) {
            for (int i = l; i <= r; i++)// 向右
                res[idx++] = matrix[u][i];

            if (d - ++u < 0)// 上下边界错开
                break;

            for (int i = u; i <= d; i++)// 向下
                res[idx++] = matrix[i][r];

            if (--r - l < 0)// 左右边界错开
                break;

            for (int i = r; i >= l; i--)// 向左
                res[idx++] = matrix[d][i];

            if (--d - u < 0)// 上下边界错开
                break;

            for (int i = d; i >= u; i--)// 向上
                res[idx++] = matrix[i][l];

            if (r - ++l < 0)// 左右边界错开
                break;

        }
        return res;
    }

    // 方法一：按层模拟（自己写的）-时间复杂度：O(mn)，空间复杂度：O(1)
    public int[] spiralOrder11(int[][] matrix) {
        int n = matrix.length;
        if (n == 0)
            return new int[] {};

        int m = matrix[0].length;
        int left = 0;
        int right = m - 1;
        int up = 0;
        int down = n - 1;
        int[] res = new int[n * m];
        int index = 0;

        while (true) {
            if (index == n * m)
                break;
            for (int j = left; j <= right; j++)
                res[index++] = matrix[up][j];
            up++;

            if (index == n * m)
                break;
            for (int i = up; i <= down; i++)
                res[index++] = matrix[i][right];
            right--;

            if (index == n * m)
                break;
            for (int j = right; j >= left; j--)
                res[index++] = matrix[down][j];
            down--;

            if (index == n * m)
                break;
            for (int i = down; i >= up; i--)
                res[index++] = matrix[i][left];
            left++;
        }
        return res;
    }

    // 剑指Offer 31.栈的压入、弹出...
    // 剑指Offer 39.数组中出现次数...

    // 剑指Offer 40.最小的k个数
    // 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

    // 方法一：排序-时间复杂度：O(nlogn)，空间复杂度：O(logn)
    // Arrays.sort()

    // 方法二：堆（优先队列）-时间复杂度：O((n-k)logk)，空间复杂度：O(logk)
    // 用一个大根堆实时维护数组的前 k 小值。首先将前 k 个数插入大根堆中，随后从第 k+1 个数开始遍历，
    // 如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] vec = new int[k];
        if (k == 0) // 排除 0 的情况
            return vec;

        // 大根堆
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>((num1, num2) -> num2 - num1);
        for (int i = 0; i < k; ++i)
            queue.offer(arr[i]);

        for (int i = k; i < arr.length; ++i)
            if (queue.peek() > arr[i]) {
                queue.poll();
                queue.offer(arr[i]);
            }

        for (int i = 0; i < k; ++i)
            vec[i] = queue.poll();

        return vec;
    }

    // 方法二：自己写的小根堆-时间复杂度：O(klogn)，空间复杂度：O(logn)
    public int[] getLeastNumbers2(int[] arr, int k) {
        int[] res = new int[k];
        if (k == 0)
            return res;

        PriorityQueue<Integer> queue = new PriorityQueue<Integer>((num1, num2) -> num1 - num2);
        for (int num : arr)
            queue.offer(num);

        for (int i = 0; i < k; i++)
            res[i] = queue.poll();

        return res;
    }

    // 方法二：基于数组的堆的实现（215.hot100有）
    int[] myNums;

    public int[] getLeastNumbers3(int[] arr, int k) {
        myNums = arr;
        int heapSize = arr.length;
        buildMaxHeap(heapSize);// 建立大根堆
        for (int i = myNums.length - 1; i >= k; --i) {// i始终指向末尾叶子节点
            swap(0, i);// 交换最大值与末尾叶子节点
            --heapSize;// 等价于删除最大值
            maxHeapify(0, heapSize);// 在指定范围内，将以i为根的子树调整为大根堆
        }
        int[] res = Arrays.copyOf(myNums, k);
        return res;
    }

    public void buildMaxHeap(int heapSize) {
        // 对于所有分支节点（节点数向下取整，非叶子节点），从后往前依次调整
        // 不能从前往后，要先处理底层，使可能沉底的最大元素逐层上浮直至最顶
        for (int i = heapSize / 2; i >= 0; --i)
            maxHeapify(i, heapSize);
    }

    // 在指定范围内，将以i为根的子树调整为大根堆（小元素下沉）
    public void maxHeapify(int root, int heapSize) {
        int l = root * 2 + 1, r = root * 2 + 2;// root节点的左右孩子
        int largest = root;
        if (l < heapSize && myNums[l] > myNums[largest])// 左孩子处于范围内且左孩子更大
            largest = l;

        if (r < heapSize && myNums[r] > myNums[largest])// 右孩子处于范围内且右孩子最大
            largest = r;

        if (largest != root) {// root不是最大的
            swap(root, largest);// 交换与最大节点
            maxHeapify(largest, heapSize);// 递归调整
        }
    }

    public void swap(int i, int j) {
        int temp = myNums[i];
        myNums[i] = myNums[j];
        myNums[j] = temp;
    }

    // 方法三：快排思想（快速选择）-时间复杂度：O(n)，具体证明可以参考《算法导论》第 9 章第 2 小节，空间复杂度：O(logn)
    public int[] getLeastNumbers4(int[] arr, int k) {
        randomizedSelected(arr, 0, arr.length - 1, k);

        int[] vec = new int[k];
        for (int i = 0; i < k; ++i)
            vec[i] = arr[i];
        return vec;
    }

    private void randomizedSelected(int[] arr, int l, int r, int k) {
        if (l >= r)// 递归中始终没有找到第k个元素，但此时一定已满足题目要求
            return;

        int pos = randomizedPartition(arr, l, r);
        if (k == pos)// 找到答案，提前返回
            return;
        else if (k < pos)// 根据num最终位置决定对左半边还是右半边进行快排
            randomizedSelected(arr, l, pos - 1, k);
        else
            randomizedSelected(arr, pos + 1, r, k);

    }

    // 基于随机的划分
    private int randomizedPartition(int[] nums, int l, int r) {
        int i = new Random().nextInt(r - l + 1) + l;
        swap(nums, r, i);// pivot放到最右边去当哨兵
        return partition(nums, l, r);
    }

    private int partition(int[] nums, int l, int r) {
        int pivot = nums[r];
        int i = l;
        for (int j = l; j < r; ++j)
            if (nums[j] <= pivot)
                swap(nums, i++, j);

        swap(nums, i, r);
        return i;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // 剑指Offer 42.连续子数组的最..
    // 剑指Offer 47.礼物的最大价值
    // 剑指Offer 51.数组中的逆序对
    // 剑指Offer 53 - I.在排序数组中...
    // 剑指Offer 53 - II.0~ n-1中缺失...
    // 剑指Offer 56 - I.数组中数字出...
    // 剑指Offer 56 - II.数组中数字出...
    // 剑指Offer 57.和为s的两个数字

    // 剑指Offer 61.扑克牌中的顺子
    // 从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。
    // 2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

    // 根据题意，此 5 张牌是顺子的 充分条件 如下：
    // 除大小王外，所有牌 无重复；
    // 设此 5 张牌中最大的牌为 max ，最小的牌为 min （大小王除外），则需满足：
    // max - min < 5
    // 因而，可将问题转化为：此 5 张牌是否满足以上两个条件

    // 方法一：集合 Set + 遍历-O(1)
    // 遍历五张牌，遇到大小王（即 0 ）直接跳过。
    // 判别重复： 利用 Set 实现遍历判重， Set 的查找方法的时间复杂度为 O(1)；
    // 获取最大 / 最小的牌： 借助辅助变量 ma 和 mi ，遍历统计即可。
    public boolean isStraight(int[] nums) {
        Set<Integer> repeat = new HashSet<>();
        int max = 0, min = 14;
        for (int num : nums) {
            if (num == 0)
                continue; // 跳过大小王
            max = Math.max(max, num); // 最大牌
            min = Math.min(min, num); // 最小牌
            if (repeat.contains(num))
                return false; // 若有重复，提前返回 false
            repeat.add(num); // 添加此牌至 Set
        }
        return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
    }

    // 方法二：排序 + 遍历-O(1)
    // 先对数组执行排序。
    // 判别重复： 排序数组中的相同元素位置相邻，因此可通过遍历数组，判断 nums[i] = nums[i + 1] 是否成立来判重。
    // 获取最大 / 最小的牌： 排序后，数组末位元素 nums[4] 为最大牌；元素 nums[joker] 为最小牌，其中 joker 为大小王的数量。
    public boolean isStraight2(int[] nums) {
        int joker = 0;
        Arrays.sort(nums); // 数组排序
        for (int i = 0; i < 4; i++) {
            if (nums[i] == 0)
                joker++; // 统计大小王数量
            else if (nums[i] == nums[i + 1])
                return false; // 若有重复，提前返回 false
        }
        return nums[4] - nums[joker] < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
    }

    // 剑指Offer 63.股票的最大利润

    // 剑指Offer 66. 构建乘积数组（238.hot100有）
    // 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积,
    // 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

    // 方法一：左右乘积列表-时间复杂度：O(n)，空间复杂度：O(n)
    // 数组 L 和 R。对于给定索引 i，L[i] 代表的是 i 左侧所有数字的乘积，R[i] 代表的是 i 右侧所有数字的乘积。

    // 方法二：找规律-时间复杂度：O(n)，空间复杂度：O(1)
    // 先把输出数组当作 L 数组来计算，然后再动态构造 R 数组得到结果
    public int[] constructArr(int[] a) {
        int length = a.length;
        int[] answer = new int[length];
        if (length == 0)
            return answer;

        // answer[i] 表示索引 i 左侧所有元素的乘积
        // 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
        answer[0] = 1;
        for (int i = 1; i < length; i++)
            answer[i] = a[i - 1] * answer[i - 1];

        // R 为右侧所有元素的乘积
        // 刚开始右边没有元素，所以 R = 1
        int R = 1;
        for (int i = length - 1; i >= 0; i--) {
            // 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
            answer[i] = answer[i] * R;
            // R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
            R *= a[i];
        }
        return answer;
    }

}

// 哈希表
class HashTableOffer {
    // 剑指Offer 03.数组中重复的数字
    // 找出数组中重复的数字。
    // 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
    // 数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
    // 请找出数组中任意一个重复的数字。
    // 限制：
    // 2 <= n <= 100000

    // 方法一：哈希表，遍历数组-时间复杂度：O(n)，空间复杂度：O(n)
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        int repeat = -1;
        for (int num : nums)
            if (!set.add(num)) {
                repeat = num;
                break;
            }

        return repeat;
    }

    // 方法二：改变原有数组结构（类似：hot100的448. 找到所有数组中消失的数字）-时间复杂度：O(n)，空间复杂度：O(1)
    // 利用在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1的特性
    int findRepeatNumber2(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int k = nums[i];// 遍历到哪个数，更改对应下标的数
            if (k < 0) // 被之前的数更改过，还原
                k += n;
            if (nums[k] < 0)// 对应下标的数被更改过，即找到重复数
                return k;
            nums[k] -= n;
        }

        return -1;
    }

    // 剑指Offer 07.重建二叉树

    // 剑指Offer 35.复杂链表的复制（138.hot100无）
    // 请实现 copyRandomList 函数，复制一个复杂链表。
    // 在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
    // 提示：
    // -10000 <= Node.val <= 10000
    // Node.random 为空（null）或指向链表中的节点。
    // 节点数目不超过 1000 。
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    // 方法一：回溯（递归） + 哈希表-时间复杂度：O(n)，空间复杂度：O(n)
    // 本题中因为随机指针的存在，当我们拷贝节点时，「当前节点的随机指针指向的节点」可能还没创建，因此我们需要变换思路。
    // 一个可行方案是，我们利用回溯的方式，让每个节点的拷贝操作相互独立。
    // 对于当前节点，我们首先要进行拷贝，然后我们进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝，
    // 拷贝完成后将创建的新节点的指针返回，即可完成当前节点的两指针的赋值。

    // 这里使用哈希表不用重写hashcode和equals方法（仅使用地址值，得到原链表和复制链表的映射）
    // 不重写hashcode方法就是返回对象的地址值，具有唯一性
    Map<Node, Node> cachedNode = new HashMap<Node, Node>();

    public Node copyRandomList(Node head) {
        if (head == null) // next或random指向null时
            return null;

        if (!cachedNode.containsKey(head)) {// 复制next时进入，复制random时不进入，只返回对应复制节点
            Node headNew = new Node(head.val);
            cachedNode.put(head, headNew);
            headNew.next = copyRandomList(head.next);// 递归调用，根据next复制完整个链表后，才开始复制random
            headNew.random = copyRandomList(head.random);// 由尾及头复制random
        }
        return cachedNode.get(head);
    }

    // 方法一：迭代 + 哈希表（自己写的）-时间复杂度：O(n)，空间复杂度：O(n)
    public Node copyRandomList11(Node head) {
        Map<Node, Node> srcDet = new HashMap<>();
        srcDet.put(null, null);// 方便找random指向
        Node dummyHead = new Node(-1);
        Node dummyNewHead = new Node(-1);
        dummyHead.next = head;
        Node newHead = dummyNewHead;
        while (head != null) {// 第一次遍历复制next，记录哈希映射
            Node newNode = new Node(head.val);
            newHead.next = newNode;
            srcDet.put(head, newNode);
            newHead = newHead.next;
            head = head.next;
        }

        head = dummyHead.next;
        newHead = dummyNewHead.next;
        while (head != null) {// 第二次遍历复制random
            newHead.random = srcDet.get(head.random);
            newHead = newHead.next;
            head = head.next;
        }
        return dummyNewHead.next;
    }

    // 方法二：迭代 + 节点拆分-时间复杂度：O(n)，空间复杂度：O(1)
    // 注意到方法一需要使用哈希表记录每一个节点对应新节点的创建情况，而我们可以使用一个小技巧来省去哈希表的空间。
    // 我们首先将该链表中每一个节点拆分为两个相连的节点，例如对于链表 A→B→C，我们可以将其拆分为A→A′→B→B′→C→C′。
    // 对于任意一个原节点 S，其拷贝节点 S′ 即为其后继节点。

    public Node copyRandomList2(Node head) {
        if (head == null)
            return null;

        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = new Node(node.val);// 复制节点
            // 复制节点插入原链表
            nodeNew.next = node.next;
            node.next = nodeNew;
        }
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = node.next;
            // 复制random指向
            nodeNew.random = (node.random != null) ? node.random.next : null;
        }
        Node headNew = head.next;
        for (Node node = head; node != null; node = node.next) {
            Node nodeNew = node.next;
            // 还原两个链表的next指向
            node.next = node.next.next;
            nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null;
        }
        return headNew;
    }

    // 剑指Offer 39.数组中出现次数超过一半的数字（169.hot100有）

    // 方法一：哈希表-时间复杂度：O(n)，空间复杂度：O(n)
    // 方法二：排序（下标为 ⌊ n/2 ⌋ 的元素一定是众数）-时间复杂度：O(nlogn)，空间复杂度：O(logn)
    // 方法三：随机化-时间复杂度为 O(n)，空间复杂度：O(1)
    // 方法四：分治-时间复杂度：O(nlogn)，空间复杂度：O(logn)

    // 方法五：Boyer-Moore 摩尔投票算法-时间复杂度为 O(n)，空间复杂度：O(1)
    // 如果我们把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。
    // 我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；
    // 我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，
    // 随后我们判断 x：
    // 如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
    // 如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
    // 在遍历完成后，candidate 即为整个数组的众数。
    public int majorityElement(int[] nums) {
        int res = -1, count = 0;
        for (int num : nums) {
            if (count == 0) {
                res = num;
                count = 1;
            } else if (num == res)
                count++;
            else
                count--;
        }
        return res;
    }

    // 剑指Offer 48.最长不含重复字符的子字符串（3.hot100有）
    // 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
    // 提示：
    // s.length <= 40000

    // 方法一：滑动窗口（自己写的）-时间复杂度：O(N)，空间复杂度：O(∣Σ∣)
    // 先移右，再移左（多次）
    public int lengthOfLongestSubstring(String s) {
        Set<Character> occ = new HashSet<>();
        int l = 0;
        int maxLength = 0;
        for (int r = 0; r < s.length(); r++) {
            if (!occ.add(s.charAt(r))) {
                char duplicate = s.charAt(r);// 重复字符
                char lchar = s.charAt(l);
                while (lchar != duplicate) {
                    occ.remove(lchar);
                    lchar = s.charAt(++l);
                }
                l++;// 找到重复字符了，左边界移动，但不删除该字符（此时右边界为该字符）
            }
            maxLength = Math.max(maxLength, r - l + 1);
        }
        return maxLength;
    }

    // 方法一：滑动窗口（自己写的）-时间复杂度：O(N)，空间复杂度：O(∣Σ∣)
    // 先移右，再移左（一次）
    public int lengthOfLongestSubstring11(String s) {
        Map<Character, Integer> charIndex = new HashMap<>();
        int left = 0;
        int right = 0;
        int res = 0;
        for (right = 0; right < s.length(); right++) {
            char curr = s.charAt(right);
            if (!charIndex.isEmpty() && charIndex.containsKey(curr)) {
                int lastOccIndex = charIndex.get(curr);
                if (lastOccIndex >= left)// 精髓所在，存在于map，但是不在[left, right]范围内，直接更新map就好
                    left = lastOccIndex + 1;
            }
            charIndex.put(curr, right);
            res = Math.max(res, right - left + 1);
        }
        return res;
    }

    // 剑指Offer 49.丑数

    // 剑指Offer 50.第一个只出现一次的字符
    // 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。
    // s 只包含小写字母。使用数组（字母表）效率要比容器高

    // 方法一：使用哈希表存储频数-时间复杂度：O(n)，空间复杂度：O(∣Σ∣)
    public char firstUniqChar(String s) {
        Map<Character, Integer> map = new LinkedHashMap<>(26);
        for (int i = 0; i < s.length(); i++) {
            char currchar = s.charAt(i);
            map.put(currchar, map.getOrDefault(currchar, 0) + 1);
        }

        Iterator<Map.Entry<Character, Integer>> iter = map.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry<Character, Integer> entry = iter.next();
            if (entry.getValue() == 1)
                return entry.getKey();

        }
        return ' ';
    }

    // 方法二：数组（同等复杂度，使用数组效率要比容器高）-时间复杂度：O(n)，空间复杂度：O(∣Σ∣)
    public char firstUniqChar2(String s) {
        int[] count = new int[26];
        char[] chars = s.toCharArray();
        for (char c : chars)
            count[c - 'a']++;

        for (char c : chars)
            if (count[c - 'a'] == 1)
                return c;

        return ' ';
    }

    // 剑指Offer 52.两个链表的第一个公共节点（160.hot100有）
    // 输入两个链表，找出它们的第一个公共节点。
    // 注意：
    // 如果两个链表没有交点，返回 null.
    // 在返回结果后，两个链表仍须保持原有的结构。
    // 可假定整个链表结构中没有循环。
    // 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

    // 方法一：哈希集合-时间复杂度：O(m+n)，空间复杂度：O(m)

    // 方法二：双指针-时间复杂度：O(m+n)，空间复杂度：O(1)

    // 剑指Offer 53 - Il. 0~ n-1中缺失的数字
    // 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
    // 在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
    // 限制：
    // 1 <= 数组长度 <= 10000

}

// 双指针
class DoublePointerOffer {
    // 剑指Offer 06.从尾到头打印链表

    // 剑指Offer 18.删除链表的节点
    // 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
    // 返回删除后的链表的头节点。

    // 方法一：迭代-时间复杂度：O(n)，空间复杂度：O(1)
    public ListNode deleteNode(ListNode head, int val) {
        if (head.val == val)// 头节点就是要删除的节点
            return head.next;
        ListNode pre = head, cur = head.next;
        while (cur != null && cur.val != val) {// 遍历到末尾或者找到要删除的节点就跳出
            pre = cur;
            cur = cur.next;
        }
        if (cur != null)// 非末尾跳出，删除当前节点
            pre.next = cur.next;
        return head;
    }

    // 剑指Offer 21.调整数组顺序使奇数位于偶数前面
    // 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

    // 方法一：双指针（左指针偶数，右指针奇数交换）-时间复杂度：O(n)，空间复杂度：O(1)
    public int[] exchange(int[] nums) {
        int i = 0, j = nums.length - 1, tmp;
        while (i < j) {
            while (i < j && (nums[i] & 1) == 1)// & 1 比 % 2 更快
                i++;
            while (i < j && (nums[j] & 1) == 0)
                j--;

            // 交换
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        return nums;
    }

    // 方法一：自己写的双指针（尽量避免使用有重复判断的嵌套while）-时间复杂度：O(n)，空间复杂度：O(1)
    public int[] exchange11(int[] nums) {
        int n = nums.length;
        int even = 0;
        int odd = n - 1;

        while (even < odd) {
            boolean evenMoved = false, oddMoved = false;
            if ((nums[even] & 1) == 1) {
                even++;
                evenMoved = true;
            }

            if ((nums[odd] & 1) == 0) {
                odd--;
                oddMoved = true;
            }

            if (!evenMoved && !oddMoved) {
                int temp = nums[even];
                nums[even] = nums[odd];
                nums[odd] = temp;
            }
        }
        return nums;
    }

    // 方法二：快慢指针（快指针指向的奇数与慢指针交换）-时间复杂度：O(n)，空间复杂度：O(1)
    // 只有快指针指向奇数时才交换，慢指针可能指向奇数，也可能指向偶数
    // 交换时，慢指针指向奇数时，为无效交换，但不影响最终结果；慢指针指向偶数时，为有效交换
    public int[] exchange2(int[] nums) {
        int slow = 0, fast = 0;
        while (fast < nums.length) {
            if ((nums[fast] & 1) == 1) {
                int temp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = temp;
                slow++;
            }
            fast++;
        }
        return nums;
    }

    // 剑指Offer 22.链表中倒数第k个节点
    // 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
    // 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

    // 方法一：顺序查找（两次遍历）-时间复杂度：O(n)，空间复杂度：O(1)
    // 首先求出链表的长度 nn，然后顺序遍历到链表的第 n - kn−k 个节点返回。

    // 方法二：双指针（快慢）-时间复杂度：O(n)，空间复杂度：O(1)
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;

        // 快指针先跑k步
        while (k > 0) {
            fast = fast.next;
            k--;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

    // 方法三：递归（自己写的）-时间复杂度：O(n)，空间复杂度：O(n)
    ListNode res;

    public ListNode getKthFromEnd3(ListNode head, int k) {
        dfs(head, k);
        return res;
    }

    private int dfs(ListNode head, int k) {
        if (head == null)
            return 1;
        int depth = dfs(head.next, k);
        if (depth == k)
            res = head;
        return depth + 1;
    }

    // 剑指Offer 41.数据流中的中位数
    // 剑指Offer 52.两个链表的第一个公共节点
    // 剑指Offer 57.和为s的两个数字

    // 剑指Offer 57 - II.和为s的连续正数序列
    // 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
    // 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

    // 方法一：枚举 + 数学优化-O(target)，空间复杂度：O(1)
    // x 累加到 y 的和由求和公式可得，转化为关于 y 的一元二次方程 y2+y−x2+x−2×target=0
    public int[][] findContinuousSequence(int target) {
        List<int[]> vec = new ArrayList<>();
        int limit = target / 2;
        for (int x = 1; x <= limit; ++x) {
            long delta = 1 - 4 * (-(long) x * x + x - 2 * target);// 防止数据溢出
            if (delta < 0)// 无解
                continue;

            int delta_sqrt = (int) Math.sqrt(delta + 0.5);
            // 保证delta开方是整数，且可行解y是整数（分子部分为偶数）
            if ((long) delta_sqrt * delta_sqrt == delta && ((-1 + delta_sqrt) & 1) == 0) {
                int y = (-1 + delta_sqrt) / 2; // 另一个解(-1-delta_sqrt)/2必然小于0，不用考虑

                // 生成序列放入List
                int[] res = new int[y - x + 1];
                for (int i = x; i <= y; ++i)
                    res[i - x] = i;
                vec.add(res);
            }
        }
        return vec.toArray(new int[vec.size()][]);
    }

    // 方法二：双指针-O(target)，空间复杂度：O(1)
    // 问题转化为（57.和为s的两个数字）
    // 用两个指针 l 和 r 表示当前枚举到的以 l 为起点到 r 的区间，sum 表示 [l,r] 的区间和，由求和公式可 O(1) 求得sum
    public int[][] findContinuousSequence2(int target) {
        List<int[]> vec = new ArrayList<int[]>();
        int l = 1;
        int r = 2;
        // 最后跳出时：target为偶数，l=r=target/2；target为奇数，l=target/2+1，r=target/2+1
        while (l < r) {
            int sum = (l + r) * (r - l + 1) / 2;
            if (sum == target) {
                int[] res = new int[r - l + 1];
                for (int i = l; i <= r; ++i)
                    res[i - l] = i;

                vec.add(res);
                l++;
            } else if (sum < target) // 指针 r 还可以向右拓展使得 sum 增大
                r++;
            else // 以 l 为起点不存在一个 r 使得 sum=target ，此时要枚举下一个起点，指针 l 向右移动
                l++;

        }
        return vec.toArray(new int[vec.size()][]);
    }

    // 剑指Offer 58 - I. 翻转单词顺序（151.hot100无，原题要求空间复杂度O(1)）
    // 输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。
    // 为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。

    // 方法一：双指针-时间复杂度，空间复杂度：O(n)
    // 倒序遍历字符串 s ，记录单词左右索引边界 i , j ；
    // 每确定一个单词的边界，则将其添加至单词列表 resres ；
    // 最终，将单词列表拼接为字符串，并返回即可。
    public String reverseWords(String s) {
        s = s.trim(); // 删除首尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while (i >= 0) {
            while (i >= 0 && s.charAt(i) != ' ')// 搜索首个空格
                i--;
            res.append(s.substring(i + 1, j + 1) + " "); // 添加单词，substring区间[ , )
            while (i >= 0 && s.charAt(i) == ' ')
                i--; // 跳过单词间空格
            j = i; // j 指向下个单词的尾字符
        }
        return res.toString().trim(); // 转化为字符串，去掉末尾空格
    }

    // 方法一：（自己写的双指针）-时间复杂度，空间复杂度：O(n)
    public String reverseWords11(String s) {
        s = s.trim();
        int n = s.length();
        int leftIndex = n - 1;
        int rightIndex = n;
        StringBuilder sb = new StringBuilder();
        while (leftIndex >= 0) {
            char curr = s.charAt(leftIndex);
            if (curr == ' ')
                rightIndex = leftIndex;
            else if (leftIndex != 0) {
                char prev = s.charAt(leftIndex - 1);
                if (prev == ' ') {
                    sb.append(s.substring(leftIndex, rightIndex));
                    sb.append(' ');
                }
            }
            leftIndex--;
        }
        sb.append(s.substring(leftIndex + 1, rightIndex));
        return new String(sb);
    }

    // 方法二：分割 + 倒序-时间复杂度，空间复杂度：O(n)
    // 利用 “字符串分割”、“列表倒序” 的内置函数 （面试时不建议使用） ，可简便地实现本题的字符串翻转要求。
    public String reverseWords2(String s) {
        String[] strs = s.trim().split(" "); // 删除首尾空格，分割字符串
        StringBuilder res = new StringBuilder();
        for (int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表
            if (strs[i].equals(""))// 遇到空单词则跳过
                continue;
            res.append(strs[i] + " "); // 将单词拼接至 StringBuilder
        }
        return res.toString().trim(); // 转化为字符串，删除尾部空格，并返回
    }

    // 剑指Offer 58 - II.左旋转字符串
    // 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。
    // 比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

    // 方法一：字符串切片-时间复杂度，空间复杂度：O(n)
    public String reverseLeftWords(String s, int n) {
        return s.substring(n, s.length()) + s.substring(0, n); // 只有一次拼接，使用+运算即可，多次则考虑StringBuilder的append方法
    }

    // 方法二：列表遍历拼接-时间复杂度，空间复杂度：O(n)
    // 若面试规定不允许使用 切片函数 ，则使用此方法。
    public String reverseLeftWords2(String s, int n) {
        StringBuilder res = new StringBuilder();
        for (int i = n; i < s.length(); i++)
            res.append(s.charAt(i));
        for (int i = 0; i < n; i++)
            res.append(s.charAt(i));
        return res.toString();
    }

    // 方法三：字符串遍历拼接
    // 若规定 Java 只能用 String ，则使用此方法。
    // 此方法与 方法二 思路一致，区别是使用String +运算代替StringBuilder的append方法。
    // 字符串是 “不可变对象” 。因此，每轮遍历拼接字符时，都需要新建一个字符串；
    // 因此，系统 需申请 N 次内存 ，数据量较大时效率低下。
    public String reverseLeftWords3(String s, int n) {
        String res = "";
        for (int i = n; i < s.length(); i++)
            res += s.charAt(i);
        for (int i = 0; i < n; i++)
            res += s.charAt(i);
        return res;
    }

}

// 字符串
class StringOffer {
    // 剑指Offer 05.替换空格-时间复杂度：O(n)，空间复杂度：O(1)
    // 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
    public String replaceSpace(String s) {
        int length = s.length();
        StringBuilder sb = new StringBuilder(length * 3);// 提前以最大值设置初始容量
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == ' ')
                sb.append("%20");
            else
                sb.append(c);
        }
        return sb.toString();
    }

    // 剑指Offer 19.正则表达式匹配

    // 剑指Offer 20.表示数值的字符串
    // 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

    // 数值（按顺序）可以分成以下几个部分：
    // 若干空格
    // 一个 小数 或者 整数
    // （可选）一个 'e' 或 'E' ，后面跟着一个 整数
    // 若干空格

    // 小数（按顺序）可以分成以下几个部分：
    // （可选）一个符号字符（'+' 或 '-'）
    // 下述格式之一：
    // 至少一位数字，后面跟着一个点 '.'
    // 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
    // 一个点 '.' ，后面跟着至少一位数字

    // 整数（按顺序）可以分成以下几个部分：
    // （可选）一个符号字符（'+' 或 '-'）
    // 至少一位数字

    // 部分数值列举如下：
    // ["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]
    // 部分非数值列举如下：
    // ["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]

    // 提示：
    // 1 <= s.length <= 20
    // s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，空格 ' ' 或者点 '.' 。

    // 方法一：确定有限状态自动机
    // 确定有限状态自动机（以下简称「自动机」）是一类计算模型。它包含一系列状态，这些状态中：有一个特殊的状态，被称作「初始状态」。
    // 还有一系列状态被称为「接受状态」，它们组成了一个特殊的集合。其中，一个状态可能既是「初始状态」，也是「接受状态」。
    // 起初，这个自动机处于「初始状态」。随后，它顺序地读取字符串中的每一个字符，并根据当前状态和读入的字符，
    // 按照某个事先约定好的「转移规则」，从当前状态转移到下一个状态；当状态转移完成后，它就读取下一个字符。
    // 当字符串全部读取完毕后，如果自动机处于某个「接受状态」，则判定该字符串「被接受」；否则，判定该字符串「被拒绝」。
    // 注意：如果输入的过程中某一步转移失败了，即不存在对应的「转移规则」，此时计算将提前中止。在这种情况下我们也判定该字符串「被拒绝」。

    // 一个自动机，总能够回答某种形式的「对于给定的输入字符串 S，判断其是否满足条件 P」的问题。
    // 在本题中，条件 P 即为「构成合法的表示数值的字符串」。

    // 自动机驱动的编程，可以被看做一种暴力枚举方法的延伸：它穷尽了在任何一种情况下，对应任何的输入，需要做的事情。
    // 自动机在计算机科学领域有着广泛的应用。
    // 在算法领域，它与大名鼎鼎的字符串查找算法「KMP」算法有着密切的关联；
    // 在工程领域，它是实现「正则表达式」的基础。

    public boolean isNumber(String s) {
        // 状态转移
        Map<State, Map<CharType, State>> transfer = new HashMap<State, Map<CharType, State>>();

        // 起始状态
        Map<CharType, State> initialMap = new HashMap<CharType, State>() {
            {
                put(CharType.CHAR_SPACE, State.STATE_INITIAL);
                put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
                put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
                put(CharType.CHAR_SIGN, State.STATE_INT_SIGN);
            }
        };
        transfer.put(State.STATE_INITIAL, initialMap);

        // 符号位
        Map<CharType, State> intSignMap = new HashMap<CharType, State>() {
            {
                put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
                put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
            }
        };
        transfer.put(State.STATE_INT_SIGN, intSignMap);

        // 整数部分
        Map<CharType, State> integerMap = new HashMap<CharType, State>() {
            {
                put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
                put(CharType.CHAR_EXP, State.STATE_EXP);
                put(CharType.CHAR_POINT, State.STATE_POINT);
                put(CharType.CHAR_SPACE, State.STATE_END);
            }
        };
        transfer.put(State.STATE_INTEGER, integerMap);

        // 小数点（左有整数）
        Map<CharType, State> pointMap = new HashMap<CharType, State>() {
            {
                put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
                put(CharType.CHAR_EXP, State.STATE_EXP);
                put(CharType.CHAR_SPACE, State.STATE_END);
            }
        };
        transfer.put(State.STATE_POINT, pointMap);

        // 小数点（左无整数）
        Map<CharType, State> pointWithoutIntMap = new HashMap<CharType, State>() {
            {
                put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
            }
        };
        transfer.put(State.STATE_POINT_WITHOUT_INT, pointWithoutIntMap);

        // 小数部分
        Map<CharType, State> fractionMap = new HashMap<CharType, State>() {
            {
                put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
                put(CharType.CHAR_EXP, State.STATE_EXP);
                put(CharType.CHAR_SPACE, State.STATE_END);
            }
        };
        transfer.put(State.STATE_FRACTION, fractionMap);

        // 字符e
        Map<CharType, State> expMap = new HashMap<CharType, State>() {
            {
                put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
                put(CharType.CHAR_SIGN, State.STATE_EXP_SIGN);
            }
        };
        transfer.put(State.STATE_EXP, expMap);

        // 指数符号
        Map<CharType, State> expSignMap = new HashMap<CharType, State>() {
            {
                put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
            }
        };
        transfer.put(State.STATE_EXP_SIGN, expSignMap);

        // 指数数字
        Map<CharType, State> expNumberMap = new HashMap<CharType, State>() {
            {
                put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
                put(CharType.CHAR_SPACE, State.STATE_END);
            }
        };
        transfer.put(State.STATE_EXP_NUMBER, expNumberMap);

        // 终止状态
        Map<CharType, State> endMap = new HashMap<CharType, State>() {
            {
                put(CharType.CHAR_SPACE, State.STATE_END);
            }
        };
        transfer.put(State.STATE_END, endMap);

        int length = s.length();
        State state = State.STATE_INITIAL;

        for (int i = 0; i < length; i++) {
            CharType type = toCharType(s.charAt(i));
            if (!transfer.get(state).containsKey(type))// type为非法状态转移，或不存在该状态转移
                return false;
            else
                state = transfer.get(state).get(type);// 下一状态

        }
        return state == State.STATE_INTEGER || state == State.STATE_POINT || state == State.STATE_FRACTION
                || state == State.STATE_EXP_NUMBER || state == State.STATE_END;
    }

    public CharType toCharType(char ch) {
        if (ch >= '0' && ch <= '9')
            return CharType.CHAR_NUMBER;
        else if (ch == 'e' || ch == 'E')
            return CharType.CHAR_EXP;
        else if (ch == '.')
            return CharType.CHAR_POINT;
        else if (ch == '+' || ch == '-')
            return CharType.CHAR_SIGN;
        else if (ch == ' ')
            return CharType.CHAR_SPACE;
        else
            return CharType.CHAR_ILLEGAL;

    }

    // 十种状态
    enum State {
        /**
         * 起始的空格
         */
        STATE_INITIAL,
        /**
         * 符号位
         */
        STATE_INT_SIGN,
        /**
         * 整数部分
         */
        STATE_INTEGER,
        /**
         * 左侧有整数的小数点
         */
        STATE_POINT,
        /**
         * 左侧无整数的小数点（根据前面的第二条额外规则，需要对左侧有无整数的两种小数点做区分）
         */
        STATE_POINT_WITHOUT_INT,
        /**
         * 小数部分
         */
        STATE_FRACTION,
        /**
         * 字符
         */
        STATE_EXP,
        /**
         * 指数部分的符号位
         */
        STATE_EXP_SIGN,
        /**
         * 指数部分的整数部分
         */
        STATE_EXP_NUMBER,
        /**
         * 末尾的空格
         */
        STATE_END
    }

    // 六种状态转移方式
    enum CharType {
        /**
         * 数字
         */
        CHAR_NUMBER,
        /**
         * 字符 e
         */
        CHAR_EXP,
        /**
         * 小数点
         */
        CHAR_POINT,
        /**
         * + - 号
         */
        CHAR_SIGN,
        /**
         * 空格
         */
        CHAR_SPACE,
        /**
         * 非法
         */
        CHAR_ILLEGAL
    }

    // 方法二：if else
    // 先判false
    public boolean isNumber2(String s) {
        char[] charArray = s.toCharArray(); // 字符数组
        int n = charArray.length;// 字符串长度
        int index = 0;// 当前下标

        // 标记
        boolean hasNum = false;
        boolean hasE = false;
        boolean hasSign = false;
        boolean hasDot = false;

        // s = s.trim();
        while (index < n && charArray[index] == ' ')// 将下标移动到非空格字符上
            index++;

        while (index < n) {// 当前下标尚未到达字符串末尾
            char c = charArray[index];// 当前字符

            if (Character.isDigit(c))// 当前字符是数字 0~9
                hasNum = true;
            else if (c == 'e' || c == 'E') {// 当前字符是 e / E
                if (hasE || !hasNum) // e / E 已经出现过，或者数字没有出现过，则该字符串必定无法表示数值，返回 false
                    return false;

                hasE = true;

                // 重置标记
                hasNum = false;
                hasSign = false;
                hasDot = false;// 主要是方便后面其他情况的判断，e后出现.时，在c=='.'中检测
            } else if (c == '+' || c == '-') {// 当前字符是正负号
                if (hasSign || hasNum || hasDot) // 如果已经出现过符号、数字、小数点，则该字符串必定无法表示数值，返回 false
                    return false;

                hasSign = true;
            } else if (c == '.') {// 如果是小数点
                if (hasDot || hasE) // 如果已经出现过小数点、e / E ，则该字符串必定无法表示数值，返回 false
                    return false;

                hasDot = true;
            } else if (c == ' ')// 如果是空格，跳出循环
                break;
            else // 非法字符
                return false;
            index++;// 继续判断下一个字符
        }

        // 如果当前下标尚未到达字符串末尾，则剩下的字符应当全部为空格，否则该字符串必定无法表示数值，返回 false
        while (index < n) {
            if (charArray[index] != ' ')
                return false;
            index++;
        }

        return hasNum;
    }

    // 方法三：javaAPI + try-catch
    public boolean isNumber3(String s) {
        if (s == null || s.length() == 0)
            return false;

        // 面向测试用例编程，末尾有空格算数字？不解
        s = s.trim();

        @SuppressWarnings("unused")
        double a;
        try {
            a = Double.parseDouble(s);
        } catch (Exception e) {
            return false;
        }

        char c = s.charAt(s.length() - 1);
        // 特，末尾有f,d,D这些不算，但是3.算数字（面向测试用例编程）
        return Character.isDigit(c) || c == '.';
        // (c >= '0' && c <= '9')
    }

    // 剑指Offer 37.序列化二叉树

    // 剑指Offer 38.字符串的排列
    // 输入一个字符串，打印出该字符串中字符的所有排列。
    // 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
    // 补充：这种没写输入细节的，直接以最坏情况考虑：字符串中存在相同字符，且可能存在特殊字符

    // 方法一：回溯（填入字符，排序后手动去除重复可能性）-时间复杂度：O(n×n!)，空间复杂度：O(n)
    // 从左往右每一个空位都依次尝试填入一个字符
    // 排序后，填入时进行相同字符去重
    // 也可以使用Set的特性放入后去重，但是效率会低不少

    List<String> rec;// 最终答案
    boolean[] vis;// 标记是否已填入

    public String[] permutation(String s) {
        int n = s.length();
        rec = new ArrayList<String>();
        vis = new boolean[n];
        char[] arr = s.toCharArray();
        Arrays.sort(arr);// 字符串中可能有重复字符，因此必须排序使得重复字符相邻
        StringBuffer perm = new StringBuffer();// 某一种答案
        backtrack(arr, 0, n, perm);// 回溯

        int size = rec.size();
        String[] recArr = rec.toArray(new String[size]);
        return recArr;
    }

    // 当前位置，最终长度
    public void backtrack(char[] arr, int i, int n, StringBuffer perm) {
        if (i == n) { // 当前情况加入最终答案
            rec.add(new String(perm));
            return;
        }

        for (int j = 0; j < n; j++) {// 依次填入当前位
            // 两种情况下跳过:
            // 当前字符已填入；
            if (vis[j])
                continue;
            // （精髓所在）当前位与前一位相同，且前一位未填入（说明相同字符已经在该位置试填入过，若前一位填入过，则一定是在其他位置上）
            if (j > 0 && arr[j - 1] == arr[j] && !vis[j - 1])
                continue;

            vis[j] = true;// 标记
            perm.append(arr[j]);
            backtrack(arr, i + 1, n, perm);

            // 还原
            perm.deleteCharAt(perm.length() - 1);
            vis[j] = false;
        }
    }

    // 方法一：回溯（填入字符，排序后手动去除重复可能性）自己写的-时间复杂度：O(n×n!)，空间复杂度：O(n)
    // List<String> res = new ArrayList<>();
    StringBuilder ans = new StringBuilder();
    int n;
    boolean used[];
    char[] chars;

    public String[] permutation11(String s) {
        n = s.length();
        used = new boolean[n];
        chars = s.toCharArray();
        Arrays.sort(chars);
        dfs38(0);
        return res.toArray(new String[res.size()]);
    }

    private void dfs38(int index) {
        if (index == n) {
            res.add(new String(ans));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (used[i])
                continue;
            if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1])
                continue;

            char curr = chars[i];
            used[i] = true;
            ans.append(curr);

            dfs38(index + 1);
            used[i] = false;
            ans.deleteCharAt(ans.length() - 1);
        }
    }

    // 方法一：回溯（交换位置）-时间复杂度：O(n×n!)，空间复杂度：O(n2)
    // 通过字符交换，先固定第 1 位字符（ n 种情况）、再固定第 2 位字符（ n-1 种情况）、... 、最后固定第 n 位字符（ 1 种情况）。

    List<String> res = new LinkedList<>();
    char[] c;

    public String[] permutation2(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }

    void dfs(int x) {
        if (x == c.length - 1) {
            res.add(String.valueOf(c)); // 添加排列方案
            return;
        }

        HashSet<Character> set = new HashSet<>();// 当前位填入过哪些字符，防止重复字符填入当前位
        for (int i = x; i < c.length; i++) {// 依次交换x位开始的字符
            if (set.contains(c[i]))
                continue; // 重复，因此剪枝
            set.add(c[i]);
            swap(i, x); // 交换，将 c[i] 固定在第 x 位
            dfs(x + 1); // 开启固定第 x + 1 位字符
            swap(i, x); // 恢复交换
        }
    }

    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }

    // 方法二：下一个排列（31.hot100有）-时间复杂度：O(n×n!)，空间复杂度：O(1)
    public String[] permutation3(String s) {
        List<String> ret = new ArrayList<String>();
        char[] arr = s.toCharArray();
        Arrays.sort(arr);// 升序排序得到"最小排列"

        do {
            ret.add(new String(arr));
        } while (nextPermutation(arr));

        int size = ret.size();
        String[] retArr = ret.toArray(new String[size]);
        return retArr;
    }

    public boolean nextPermutation(char[] arr) {
        int i = arr.length - 2;
        while (i >= 0 && arr[i] >= arr[i + 1])// 从后往前，下标i即为第一个非升序数，（较小数）
            i--;

        if (i < 0)// arr已是降序（最大值），不存在下一个排列
            return false;

        int j = arr.length - 1;
        while (j >= 0 && arr[i] >= arr[j])// 从后往前（必升序），找到第一个比下标i大的数j（较大数）
            j--;

        swap(arr, i, j);// 交换左边的「较小数」与右边的「较大数」
        reverse(arr, i + 1);// 「较大数」右边的数需要按照升序重新排列，此时必为降序，翻转即可
        return true;
    }

    public void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public void reverse(char[] arr, int start) {
        int left = start, right = arr.length - 1;
        while (left < right) {
            swap(arr, left, right);
            left++;
            right--;
        }
    }

    // 剑指Offer 45.把数组排成最小的数
    // 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
    // 提示:
    // 0 < nums.length <= 100
    // 说明:
    // 输出结果可能非常大，所以你需要返回一个字符串而不是整数
    // 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

    // 方法一：定制排序 贪心-时间复杂度：O(nlogn)，空间复杂度：O(logn)
    // 此题求拼接起来的最小数字，本质上是一个排序问题。设数组 nums 中任意两数字的字符串为 x 和 y ，则规定 排序判断规则 为：
    // 若拼接字符串 x + y > y + x ，则 x “大于” y ；
    // 反之，若 x + y < y + x ，则 x “小于” y ；
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++)
            strs[i] = String.valueOf(nums[i]);
        // String[] strs =
        // Arrays.stream(nums).mapToObj(String::valueOf).toArray(String[]::new);
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder res = new StringBuilder();
        for (String s : strs)
            res.append(s);
        return res.toString();
    }

    // 剑指Offer 46.把数字翻译成字...
    // 剑指Offer 48.最长不含重复字...
    // 剑指Offer 50.第一个只出现...
    // 剑指Offer 58- I.翻转单词顺序;
    // 剑指Offer 58- II.左旋转字符串:

    // 剑指Offer 67.把字符串转换成整数（8.hot100无）
    // 写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
    // 首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
    // 当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，
    // 作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
    // 该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
    // 注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
    // 在任何情况下，若函数不能进行有效的转换时，请返回 0。
    // 说明：
    // 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−2^31,  2^31 − 1]。
    // 如果数值超过这个范围，请返回  INT_MAX (2^31 − 1) 或 INT_MIN (−2^31) 。

    // 方法一：if else-时间复杂度：O(n)，空间复杂度：O(1)
    // 1.首部空格： 删除之即可；
    // 2.符号位： 三种情况，即 "+" , "−" , "无符号" ；新建一个变量保存符号位，返回前判断正负即可。
    // 3.非数字字符： 遇到首个非数字的字符时，应立即返回。
    // 4.数字字符：
    // 4.1.字符转数字： “此数字的 ASCII 码” 与 “ 0 的 ASCII 码” 相减即可；（题目要求不能使用字符串转数字的库函数）
    // 4.2.数字拼接
    public int strToInt(String str) {
        int res = 0, bndry = Integer.MAX_VALUE / 10;
        int i = 0;
        int sign = 1;// 符号位
        int length = str.length();
        if (length == 0)
            return 0;
        while (str.charAt(i) == ' ')// 跳过首部空格
            if (++i == length)// 全是空格
                return 0;

        // 处理符号位
        if (str.charAt(i) == '-')
            sign = -1;
        if (str.charAt(i) == '-' || str.charAt(i) == '+')
            i++;

        // 开始转换整数
        for (int j = i; j < length; j++) {
            if (str.charAt(j) < '0' || str.charAt(j) > '9')// 读到非数字，空格、字符等
                break;
            if (res > bndry || (res == bndry && str.charAt(j) > '7')) // 判断是否越界 int MAX_VALUE = 2147483647
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE; // int MIN_VALUE = -2147483648
            res = res * 10 + (str.charAt(j) - '0');
        }
        return sign * res;
    }

    // 方法一：（自己写的）if else
    public int strToInt11(String str) {
        str = str.trim();
        if (str.length() == 0)
            return 0;
        boolean hasSign = false;
        int i = 0;
        if (str.charAt(0) == '-') {
            hasSign = true;
            i++;
        } else if (str.charAt(0) == '+')
            i++;

        int num = 0;
        for (; i < str.length(); i++) {
            char curr = str.charAt(i);
            if (!Character.isDigit(curr))
                break;

            int currNum = curr - '0';
            if (hasSign) {
                if (num > Integer.MAX_VALUE / 10)
                    return Integer.MIN_VALUE;
                if (num == Integer.MAX_VALUE / 10 && currNum >= Integer.MAX_VALUE % 10 + 1)
                    return Integer.MIN_VALUE;
            } else {
                if (num > Integer.MAX_VALUE / 10)
                    return Integer.MAX_VALUE;
                if (num == Integer.MAX_VALUE / 10 && currNum >= Integer.MAX_VALUE % 10)
                    return Integer.MAX_VALUE;
            }
            num = num * 10 + currNum;
        }

        if (hasSign)
            return num * -1;
        else
            return num;
    }

    // 方法二：有限状态机-时间复杂度：O(n)，空间复杂度：O(1)
    public int strToInt2(String str) {
        Automaton automaton = new Automaton();
        int length = str.length();
        for (int i = 0; i < length; ++i)
            automaton.get(str.charAt(i));

        return (int) (automaton.sign * automaton.ans);
    }

    class Automaton {
        public int sign = 1;// 符号标记
        public long ans = 0;
        private String state = "start";// 起始状态
        private Map<String, String[]> table = new HashMap<String, String[]>() {
            {
                // 状态转移方式 ' ' +/- number other
                // 起始状态
                put("start", new String[] { "start", "signed", "in_number", "end" });
                // 符号
                put("signed", new String[] { "end", "end", "in_number", "end" });
                // 数字
                put("in_number", new String[] { "end", "end", "in_number", "end" });
                // 终止状态
                put("end", new String[] { "end", "end", "end", "end" });
            }
        };

        // 状态转移
        public void get(char c) {
            state = table.get(state)[get_col(c)];
            if ("in_number".equals(state)) {// 数字状态，计算答案
                ans = ans * 10 + c - '0';
                ans = sign == 1 ? Math.min(ans, (long) Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE);
            } else if ("signed".equals(state))// 符号状态，记录正负
                sign = c == '+' ? 1 : -1;

        }

        // 状态转移方式 ' ' +/- number other
        private int get_col(char c) {
            if (c == ' ')
                return 0;
            if (c == '+' || c == '-')
                return 1;
            if (Character.isDigit(c))
                return 2;
            return 3;
        }
    }
}

// 二分查找
class BinarySearchOffer {
    // 剑指Offer 04.二维数组中的查找（240.hot100有）
    // 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
    // 请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
    // 方法一：直接查找-时间复杂度：O(mn)
    // 方法二：二分查找-时间复杂度：O(mlogn)
    // 由于矩阵 matrix 中每一行的元素都是升序排列的，因此我们可以对每一行都使用一次二分查找
    public boolean searchMatrix2(int[][] matrix, int target) {
        for (int[] row : matrix) {
            int index = biSearch(row, target);
            if (index >= 0)
                return true;

        }
        return false;
    }

    public int biSearch(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target)
                return mid;
            else if (num > target)
                high = mid - 1;
            else
                low = mid + 1;

        }
        return -1;
    }

    // 方法三：Z 字形查找-时间复杂度：O(m+n)，空间复杂度：O(1)
    // 从矩阵 matrix 的右上角 (0, n-1) 进行搜索。在每一步的搜索过程中，如果我们位于位置 (x, y)，
    // 那么我们希望在以 matrix 的左下角为左下角、以 (x, y) 为右上角的矩阵中进行搜索，
    // 即行的范围为 [x, m - 1]，列的范围为 [0, y]：
    public boolean searchMatrix3(int[][] matrix, int target) {
        int m = matrix.length;
        if (m == 0)
            return false;
        int n = matrix[0].length;
        int x = 0, y = n - 1;
        while (x < m && y >= 0) {
            if (matrix[x][y] == target)
                return true;

            if (matrix[x][y] > target)// matrix[x][y]往下也一定大于target，丢弃该列
                --y;
            else// matrix[x][y]往左一定小于target，丢弃该行
                ++x;
        }
        return false;
    }

    // 剑指Offer 11.旋转数组的最小数字（153.154.hot100无 33.搜索旋转排序数组hot100有）
    // 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
    // 给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。
    // 请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为1。  

    // 方法一：二分查找-时间复杂度：O(logn)，空间复杂度： O(1)
    // 全部跟右边界比
    // 这道题非常特殊，不属于找到第一个大于某值的数，而属于找到等于某值的数
    // 由于重复元素的存在，我们并不能确定 numbers[pivot] 究竟在最小值的左侧还是右侧，因此我们不能莽撞地忽略某一部分的元素。
    // e.g. 33133 33331这种混淆情况，需要与右边界对比，相等则右边界--
    public int minArray(int[] numbers) {
        int low = 0;
        int high = numbers.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;// 防止数据溢出
            if (numbers[pivot] < numbers[high])
                high = pivot;
            else if (numbers[pivot] > numbers[high])
                low = pivot + 1;
            else
                high -= 1;

        }
        return numbers[low];
    }

    // 剑指Offer 44.数字序列中某一位的数字（400.hot100有，但是是从1开始）
    // 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
    // 请写一个函数，求任意第n位对应的数字。\
    // 限制：
    // 0 <= n < 2^31
    // 测试是从1开始（无语）

    // 方法一：直接查找 找规律-时间复杂度：O(logn)，空间复杂度：O(1)
    public int findNthDigit(int n) {

        int d = 1;// 当前遍历到的「位数」
        int count = 9;// 「当前位数下的所有整数的个数」
        while (n > (long) d * count) {// 最后一下防越界（10位数）
            n -= d * count;
            d++;
            count *= 10;
        }
        int index = n - 1;
        int start = (int) Math.pow(10, d - 1);// 从这个数开始
        int num = start + index / d;// 第n位数字所在的数
        int digitIndex = index % d;// 第n位数字在所在数中的下标

        return (num / (int) (Math.pow(10, d - digitIndex - 1))) % 10;// 空间复杂度：O(1)
        // return Integer.toString(num).charAt(digitIndex) - '0'; // 3.字符作差求值 空间复杂度：O(n)
        // return String.valueOf(whichNum).charAt(indexInNum)-'0';

    }

    // 方法二：二分查找（找位数，有点强行）-时间复杂度：O(logn×loglogn)，空间复杂度：O(1)
    public int findNthDigit2(int n) {
        // MAX_VALUE = 2147483647
        // 若计算10位数的totalDigits(10)会越界
        int low = 1, high = 9;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (totalDigits(mid) < n)
                low = mid + 1;
            else
                high = mid;
        }
        int digits = low;
        int prevDigits = totalDigits(digits - 1);
        int index = n - prevDigits - 1;
        int start = (int) Math.pow(10, digits - 1);
        int num = start + index / digits;
        int digitIndex = index % digits;

        return (num / (int) (Math.pow(10, digits - digitIndex - 1))) % 10;
    }

    // 「length位数及之前位数，所有数的位数和」9 + 90 + 900+...
    public int totalDigits(int length) {
        int digits = 0;
        int curLength = 1, curCount = 9;
        while (curLength <= length) {
            digits += curLength * curCount;
            curLength++;
            curCount *= 10;
        }
        return digits;
    }

    // 剑指Offer 51.数组中的逆序对
    // 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

    // 方法一：归并排序-时间复杂度：同归并排序 O(nlogn)，空间复杂度：同归并排序 O(n)，因为归并排序需要用到一个临时数组。
    // 「归并排序」是分治思想的典型应用，它包含这样三个步骤：
    // 分解： 待排序的区间为 [l, r]，把 [l, r] 分成 [l, m] 和 [m + 1, r]
    // 解决： 使用归并排序递归地排序两个子序列
    // 合并： 把两个已经排好序的子序列 [l, m] 和 [m + 1, r] 合并起来
    // 在待排序序列长度为 1 的时候，递归开始「回升」，因为我们默认长度为 1 的序列是排好序的。

    // 那么求逆序对和归并排序又有什么关系呢？关键就在于「归并」当中「并」的过程。
    // 合并 2 个有序子序列时，归并的同时可以计算新增的逆序对数量。
    public int reversePairs(int[] nums) {
        int len = nums.length;

        if (len < 2) // 特殊情况
            return 0;

        int[] temp = new int[len];//拷贝数组
        return reversePairs(nums, 0, len - 1, temp);
    }

    private int reversePairs(int[] nums, int left, int right, int[] temp) {
        // 问题的最小长度
        if (left == right)
            return 0;

        int mid = left + (right - left) / 2;// 防止加和数据溢出
        // 问题分解
        int leftPairs = reversePairs(nums, left, mid, temp);
        int rightPairs = reversePairs(nums, mid + 1, right, temp);

        if (nums[mid] <= nums[mid + 1])// 两个子序列为升序，无需归并，逆序对数量不变
            return leftPairs + rightPairs;

        int crossPairs = mergeAndCount(nums, left, mid, right, temp);// 归并，同时计算新增逆序对数量
        return leftPairs + rightPairs + crossPairs;
    }

    private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
        for (int i = left; i <= right; i++)// 拷贝要归并的部分
            temp[i] = nums[i];

        int i = left;// 左子序列起始下标
        int j = mid + 1;// 右子序列起始下标

        int count = 0;
        for (int k = left; k <= right; k++) {// 根据拷贝部分，把最终归并结果放入nums数组

            if (i == mid + 1) {// 此时所有左子序列已放入nums数组中，直接将右子序列当前位置放入nums数组中即可
                nums[k] = temp[j];
                j++;
            } else if (j == right + 1) {// 同上，此时所有右子序列已放入nums数组中
                nums[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {// 左子序列更小，放入nums数组，数值相等时，优先放入左子序列中的数
                nums[k] = temp[i];
                i++;
            } else {// 右子序列更小，放入nums数组
                nums[k] = temp[j];
                j++;
                count += (mid + 1 - i); // 计算新增逆序对数量
                // 放入右子序列时计数，个数为，左子序列指针i到mid之间的个数
                // 好处是：（对比放入左子序列时计数）由于相等时优先放入左子序列中的数，放入右子序列时再计数，计数一定正确
                // 所有左子序列放入数组后，count计数+0，不用单独在条件(i == mid + 1)处计数
            }
        }
        return count;
    }

    // 方法一：（自己写的）归并排序-时间复杂度：同归并排序 O(nlogn)，空间复杂度：同归并排序 O(n)，因为归并排序需要用到一个临时数组。
    int nums[];
    int temp[];

    public int reversePairs11(int[] nums) {
        int n = nums.length;
        this.nums = nums;
        this.temp = new int[n];
        return partition(0, n - 1);
    }

    // 先划分再归并
    private int partition(int left, int right) {
        if (left >= right)
            return 0;
        int mid = (left + right) / 2;
        int leftPairs = partition(left, mid);
        int rightPairs = partition(mid + 1, right);
        int curPairs = merge(left, right, mid);
        return leftPairs + rightPairs + curPairs;
    }

    private int merge(int left, int right, int mid) {
        int pairs = 0;
        for (int i = left; i <= right; i++)
            temp[i] = nums[i];

        int i = left;
        int j = mid + 1;
        while (i <= mid && j <= right) {

            int x = temp[i];
            int y = temp[j];
            if (x > y) {
                nums[left] = y;
                pairs += mid - i + 1;
                left++;
                j++;
            } else if (x <= y) {
                nums[left] = x;
                left++;
                i++;
            }

        }

        if (i > mid)
            for (int index = j; index <= right; index++)
                nums[left++] = temp[index];

        if (j > right)
            for (int index = i; index <= mid; index++)
                nums[left++] = temp[index];

        return pairs;
    }

    // 方法二：离散化树状数组
    // 时间复杂度：离散化的过程中使用了时间代价为 O(nlogn) 的排序，单次二分的时间代价为 O(logn)，一共有 n 次，
    // 总时间代价为 O(nlogn)；循环执行 n 次，每次进行 O(logn) 的修改和 O(logn) 的查找，总时间代价为 O(nlogn)。
    // 故渐进时间复杂度为 (nlogn)。
    // 空间复杂度：树状数组需要使用长度为 n 的数组作为辅助空间，故渐进空间复杂度为 O(n)

    // 「树状数组」是一种可以动态维护序列前缀和的数据结构，它的功能是：
    // 单点更新 update(i, v)： 把序列 i 位置的数加上一个值 v，这题 v = 1
    // 区间查询 query(i)： 查询序列 [1⋯i] 区间的区间和，即 i 位置的前缀和
    // 修改和查询的时间代价都是 O(logn)，其中 n 为需要维护前缀和的序列的长度。

    // 从后往前遍历序列 a，记当前遍历到的元素为 ai，我们把 ai 对应的桶的值自增 1，把 i−1 位置的前缀和加入到答案中算贡献。
    public int reversePairs2(int[] nums) {
        int n = nums.length;
        int[] tmp = new int[n];
        System.arraycopy(nums, 0, tmp, 0, n);
        // 离散化
        Arrays.sort(tmp);
        for (int i = 0; i < n; ++i)
            nums[i] = Arrays.binarySearch(tmp, nums[i]) + 1;

        // 树状数组统计逆序对
        BIT bit = new BIT(n);
        int ans = 0;
        for (int i = n - 1; i >= 0; --i) {
            ans += bit.query(nums[i] - 1);
            bit.update(nums[i]);
        }
        return ans;
    }

    class BIT {
        private int[] tree;
        private int n;

        public BIT(int n) {
            this.n = n;
            this.tree = new int[n + 1];
        }

        public int lowbit(int x) {
            return x & (-x);
        }

        public int query(int x) {
            int ret = 0;
            while (x != 0) {
                ret += tree[x];
                x -= lowbit(x);
            }
            return ret;
        }

        public void update(int x) {
            while (x <= n) {
                ++tree[x];
                x += lowbit(x);
            }
        }
    }

    // 剑指Offer 53 - I.在排序数组中查找数字 I（34.hot100有）
    // 统计一个数字在排序数组中出现的次数。

    // 方法一：二分法-时间复杂度：O(logn)，空间复杂度：O(1)
    public int search(int[] nums, int target) {
        int leftIndex = binarySearch(nums, target - 1);
        int rightIndex = binarySearch(nums, target) - 1;
        if (leftIndex <= rightIndex && nums[leftIndex] == target)
            return rightIndex - leftIndex + 1;
        return 0;
    }

    // 返回第一个大于target的数的下标
    private int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return left;
    }

    // 方法一：（自己写的）二分法-时间复杂度：O(logn)，空间复杂度：O(1)
    int[] nums53;

    public int search11(int[] nums, int target) {
        this.nums53 = nums;
        int startIndex = findFirstAppear(target);
        int endIndex = findFirstAppear(target + 1) - 1;
        return endIndex - startIndex + 1;
    }

    private int findFirstAppear(int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums53[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return left;
    }

    // 剑指Offer 53- II. 0~n-1中缺失的数字
    // 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
    // 在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

    // 方法一：二分法-时间复杂度 O(logN)，空间复杂度 O(1)
    public int missingNumber(int[] nums) {

        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == mid)
                left = mid + 1;
            else
                right = mid - 1;

        }
        return left;
    }

    // 剑指Offer 57.和为s的两个数字
    // 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。
    // 如果有多对数字的和等于s，则「输出任意一对即可」。

    // 方法一：对小于target/2的数依次二分查找与target的差值-时间复杂度 O(nlogn)，空间复杂度 O(1)

    // 方法二：双指针-时间复杂度 O(n)，空间复杂度 O(1)
    public int[] twoSum(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while (i < j) {
            int s = nums[i] + nums[j];
            if (s < target)// 要增大s只能右移i
                i++;
            else if (s > target)// 要减小s只能左移j
                j--;
            else
                return new int[] { nums[i], nums[j] };
        }
        return new int[0];
    }

}

// 动态规划
class DynamicProgrammingOffer {
    // 剑指Offer 10- I.斐波那契数列
    // 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
    // F(0) = 0,   F(1) = 1
    // F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
    // 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
    // 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
    // 提示：
    // 0 <= n <= 100

    // 方法一：动态规划-时间复杂度：O(n)，空间复杂度：O(1)
    // 滚动数组
    public int fib(int n) {
        final int MOD = 1000000007;
        if (n < 2)
            return n;

        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q;
            q = r;
            r = (int) (((long) p + q) % MOD);// 只在加法结果取模就行了
        }
        return r;
    }

    // 方法一：动态规划（自己写的，就注意下数据溢出和取模）-时间复杂度：O(n)，空间复杂度：O(1)
    public int fib11(int n) {
        long dp0 = 0;
        long dp1 = 1;
        if (n == 0)
            return (int) dp0;
        for (int i = 2; i <= n; i++) {
            long dp2 = (dp0 + dp1) % 1000000007;
            dp0 = dp1;
            dp1 = dp2;
        }
        return (int) dp1;
    }

    // 方法二：矩阵快速幂-时间复杂度：O(logn)，空间复杂度：O(1)
    // 递推关系式可写成：[][]=[]
    // 最终答案与初始条件之间的关系[]=[]^n []
    public int fib2(int n) {
        if (n < 2)
            return n;

        int[][] q = { { 1, 1 }, { 1, 0 } };
        int[][] res = pow(q, n - 1);
        return res[0][0];
    }

    // 快速幂
    public int[][] pow(int[][] a, int n) {
        int[][] ret = { { 1, 0 }, { 0, 1 } };// 此时[ret][a] = [a]
        while (n > 0) {
            if ((n & 1) == 1)// n为奇数时
                ret = multiply(ret, a);

            n >>= 1;
            a = multiply(a, a);
        }
        return ret; // 最终答案为：n为奇数时，a的乘积
    }

    // 矩阵运算
    public int[][] multiply(int[][] a, int[][] b) {
        final int MOD = 1000000007;
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                c[i][j] = (int) (((long) a[i][0] * b[0][j] + (long) a[i][1] * b[1][j]) % MOD);// 先扩容再取模

        return c;
    }

    // 方法二：自己写的快速幂
    long C = 1000000007;

    public int fib22(int n) {
        long[] res = new long[] { 0, 1 };
        if (n < 2)
            return (int) res[n];

        int times = n - 1;
        long matrix[][] = new long[][] { { 1, 0 }, { 0, 1 } };
        long temp[][] = new long[][] { { 0, 1 }, { 1, 1 } };
        while (times != 0) {
            if (times % 2 == 1)
                matrix = pow2(matrix, temp);
            times = times / 2;
            temp = pow2(temp, temp);
        }
        return (int) (res[0] * matrix[0][1]) + (int) (res[1] * matrix[1][1]);

    }

    private long[][] pow2(long[][] matrix1, long[][] matrix2) {
        long[][] ans = new long[2][2];
        long a = matrix1[0][0];
        long b = matrix1[0][1];
        long c = matrix1[1][0];
        long d = matrix1[1][1];

        long e = matrix2[0][0];
        long f = matrix2[0][1];
        long g = matrix2[1][0];
        long h = matrix2[1][1];

        ans[0][0] = (a * e + b * g) % C;
        ans[0][1] = (a * f + b * h) % C;
        ans[1][0] = (c * e + d * g) % C;
        ans[1][1] = (c * f + d * h) % C;
        return ans;
    }

    // 方法三：递归+记忆化搜索

    // 剑指Offer 10- II.青蛙跳台阶问题（70.hot100有）
    // 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
    // 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
    // 提示：
    // 0 <= n <= 100

    // 剑指Offer 13.机器人的运动范围
    // 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，
    // 它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。
    // 例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。
    // 请问该机器人能够到达多少个格子？
    // 提示：
    // 1 <= n,m <= 100
    // 0 <= k <= 20
    // 方法一：广度优先搜索 bfs-时间复杂度：O(mn)，空间复杂度：O(mn)
    public int movingCount(int m, int n, int k) {
        if (k == 0)
            return 1;

        // 辅助队列存放可达坐标
        Queue<int[]> queue = new LinkedList<int[]>();
        // 向右和向下的方向数组
        int[] dx = { 0, 1 };
        int[] dy = { 1, 0 };
        boolean[][] vis = new boolean[m][n];// 是否可达
        queue.offer(new int[] { 0, 0 });// 初始节点入队
        vis[0][0] = true;
        int ans = 1;
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int x = cell[0], y = cell[1];
            for (int i = 0; i < 2; ++i) {// 向右向下两个方向遍历，0向下，1向右
                int tx = dx[i] + x;
                int ty = dy[i] + y;

                // 向下向右越界；或已访问过；或坐标数位和 > k
                if (tx >= m || ty >= n || vis[tx][ty] || get(tx) + get(ty) > k)
                    continue;

                queue.offer(new int[] { tx, ty });
                vis[tx][ty] = true;
                ans++;
            }
        }
        return ans;
    }

    private int get(int x) {
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }

    // 方法二：dfs

    // 方法三：递推（动态规划）-时间复杂度：O(mn)，空间复杂度：O(mn)
    public int movingCount2(int m, int n, int k) {
        if (k == 0)
            return 1;

        boolean[][] vis = new boolean[m][n];
        int ans = 1;
        vis[0][0] = true;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if ((i == 0 && j == 0) || get(i) + get(j) > k)
                    continue;

                // 边界判断
                if (i > 0)// 左可达
                    vis[i][j] |= vis[i - 1][j];

                if (j > 0)// 上可达
                    vis[i][j] |= vis[i][j - 1];

                ans += vis[i][j] ? 1 : 0;
            }
        }
        return ans;
    }
    // private int get(int x);

    // 剑指Offer 14- I.剪绳子（343.）
    // 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且「m>1」），
    // 每段绳子的长度记为 k[0],k[1]...k[m-1]。
    // 请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？
    // 例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
    // 提示：
    // 2 <= n <= 58

    // 方法一：动态规划-时间复杂度：O(n^2)，空间复杂度：O(n)
    public int cuttingRope(int n) {
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {// 绳长为i
            int curMax = 0;
            for (int j = 1; j < i / 2 + 1; j++)// 拆分成 j * (i-j) 时的最大乘积
                curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));// 这里可优化

            dp[i] = curMax;
        }
        return dp[n];
    }

    // 方法二：优化的动态规划-时间复杂度：O(n)，空间复杂度：O(n)
    // dp[2] = 1;// 1 * 1
    // dp[3] = 2;// 1 * 2
    // 以上，绳长大于乘积（即不如不拆）
    // dp[4] = 4;// 2 * 2（拆不拆不影响）
    // dp[5] = 6;// 2 * 3（必拆）
    // dp[6] = 9;// 3 * 3（必拆）
    public int cuttingRope2(int n) {
        // dp[2] = 1;// 1 * 1
        // dp[3] = 2;// 1 * 2
        if (n < 4)
            return n - 1;

        int[] dp = new int[n + 1];
        // i = 2, 3时不继续拆
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i <= n; i++)
            dp[i] = Math.max(2 * dp[i - 2], 3 * dp[i - 3]);

        return dp[n];
    }

    // 方法二：自己写的动态规划-时间复杂度：O(n)，空间复杂度：O(n)
    public int cuttingRope22(int n) {
        int dp[] = new int[n + 1];
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 2; j <= 3; j++) {
                int left = Math.max(dp[j], j);
                int right = Math.max(dp[i - j], i - j);
                dp[i] = Math.max(dp[i], left * right);
            }
        }
        return dp[n];
    }

    // 方法三：数学-时间复杂度：O(1)，空间复杂度：O(1)
    // 归纳证明法
    // 第一步：证明最优的拆分方案中不会出现大于 4 的整数。
    // 假设出现了大于 4 的整数 x，由于 2(x-2) > x 在 x > 4 时恒成立，将 x 拆分成 2 和 x-2 可以增大乘积。
    // 因此最优的拆分方案中不会出现大于 4 的整数。
    // 第二步：证明最优的拆分方案中可以不出现整数 4。
    // 如果出现了整数 4，我们可以用 2×2 代替之，乘积不变。
    // 此时，我们可以知道，最优的拆分方案中只会出现 1，2 和 3。
    // 第三步：证明当 n≥5 时，最优的拆分方案中不会出现整数 1。
    // 当 n≥5 时，如果出现了整数 1，那么拆分中剩余的数的和为 n−1≥4，对应这至少两个整数。
    // 我们将其中任意一个整数 x 加上 1，乘积就会增大。因此最优的拆分方案中不会出现整数 1。
    // 此时，我们可以知道，当 n≥5 时，最优的拆分方案中只会出现 2 和 3。
    // 第四步：证明当 n≥5 时，最优的拆分方案中 2 的个数不会超过 3 个。
    // 如果出现了超过 3 个 2，那么将它们转换成 2 个 3，可以增大乘积，即3×3>2×2×2。

    // 此时，n≥5 的最优拆分方案就唯一了。这是因为当最优的拆分方案中 2 的个数分别为 0，1，2 个时，
    // 就对应着 n 除以 3 的余数分别为 0，2，1 的情况。因此我们可以得到和「函数极值证明法」相同的分类讨论结果。
    // 当 n = 4 时，4=2×2 的最优拆分方案也可以放入分类讨论结果；当 2≤n≤3 时，
    // 只有唯一的拆分方案 1×(n−1)。
    public int cuttingRope3(int n) {
        if (n <= 3)
            return n - 1;

        int quotient = n / 3;
        int remainder = n % 3;
        if (remainder == 0)// 余0，全拆成3
            return (int) Math.pow(3, quotient);// 零个2
        else if (remainder == 1)// 余1，拆两个2，其余全3
            return (int) Math.pow(3, quotient - 1) * 4;// 两个2
        else// 余2，拆一个2，其余全3
            return (int) Math.pow(3, quotient) * 2;// 一个2

    }

    // 剑指Offer 14- I.剪绳子II（343.hot100无）
    // 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），
    // 每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？
    // 例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
    // 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
    // 提示：
    // 2 <= n <= 1000

    // 动态规划没法用，因为要在中间计算中取模1e9+7，绝对大小发生变化，后续计算得不到正确结果
    // 重写一下之前Math.Pow
    // 方法一：数学+快速幂-时间复杂度：O(logn)，空间复杂度：O(1)
    public int cuttingRope4(int n) {
        if (n <= 3)
            return n - 1;

        int quotient = n / 3;
        int remainder = n % 3;
        if (remainder == 0)// 余0，全拆成3
            return myPow(3, quotient);// 零个2
        else if (remainder == 1)// 余1，拆两个2，其余全3
            return multiply(myPow(3, quotient - 1), 4);// 两个2
        else// 余2，拆一个2，其余全3
            return multiply(myPow(3, quotient), 2);// 一个2
    }

    // 快速幂
    public int myPow(int a, int n) {
        int ret = 1;// 系数
        while (n > 0) {
            if ((n & 1) == 1)// n为奇数时
                ret = multiply(ret, a);

            n >>= 1;
            a = multiply(a, a);
        }
        return ret; // 最终答案为：n为奇数时，a的乘积
    }

    // 矩阵运算
    public int multiply(int a, int b) {
        final int MOD = 1000000007;
        int c = (int) (((long) a * b) % MOD);// 先扩容再取模
        return c;
    }

    // 剑指Offer 19.正则表达式匹配（10.hot100有）
    // 请实现一个函数用来匹配包含'. '和'*'的正则表达式。
    // 模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。
    // 在本题中，匹配是指字符串的所有字符匹配整个模式。
    // 例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。
    // s 可能为空，且只包含从 a-z 的小写字母。
    // p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。

    // 方法一：动态规划-时间复杂度、空间复杂度：O(mn)
    // 对匹配的方案进行枚举：
    // f[i][j] 表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配。（注意第几个字符与索引的对应）
    String s;
    String p;

    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        this.s = s;
        this.p = p;

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i)// 前 i 个字符
            for (int j = 1; j <= n; ++j) {// 前 j 个字符
                if (p.charAt(j - 1) == '*') {// 第j个字符为*（对应下标j-1）
                    // *前字符匹配 s 末尾的一个字符，将该字符扔掉，而该组合还可以继续进行匹配，
                    // 继承上一状态（看做出现次数+1，或者成功了也不匹配）
                    if (matches(i, j - 1))
                        f[i][j] = f[i - 1][j] || f[i][j - 2];

                    // *前字符不匹配字符，将该组合扔掉，不再进行匹配，继承上一状态（看做是出现次数为0）
                    else
                        f[i][j] = f[i][j - 2];

                } else {// 第j个字符为字母或.
                    if (matches(i, j))
                        f[i][j] = f[i - 1][j - 1];// 匹配则继承上一状态（单字符匹配）
                    // 不匹配则为默认值fasle
                }
            }

        return f[m][n];
    }

    // 字符的比较（比较s中第i个字符和p中第j个字符）
    public boolean matches(int i, int j) {
        if (i == 0)// 字符串长度为0，一定不匹配
            return false;

        if (p.charAt(j - 1) == '.')// 一定匹配
            return true;

        return s.charAt(i - 1) == p.charAt(j - 1);
    }

    // 剑指Offer 42.连续子数组的最大和（53.hot100有）
    // 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
    // 要求时间复杂度为O(n)。

    // 方法一：动态规划-时间复杂度：O(n)，空间复杂度：O(1)
    // 动态规划转移方程：f(i) = max{f(i−1)+nums[i], nums[i]}
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }

    // 方法二：分治（线段树）-时间复杂度：O(n)，空间复杂度：O(logn)
    // 取 m = (l+r)/2，对区间 [l,m] 和 [m+1,r] 分治求解
    // 对于一个区间 [l,r]，我们可以维护四个量：
    // lSum 表示 [l,r] 内以 l 为左端点的最大子段和
    // rSum 表示 [l,r] 内以 r 为右端点的最大子段和
    // iSum 表示 [l,r] 的区间和
    // mSum 表示 [l,r] 内的最大子段和
    // 考虑 [l,r] 的 mSum 对应的区间是否跨越 m

    // 方法二的意义：
    // 线段树不仅可以解决区间 [0, n-1]，还可以用于解决任意的子区间 [l,r] 的问题。
    // 如果我们把 [0, n-1] 分治下去出现的所有子区间的信息都用堆式存储的方式记忆化下来，
    // 即建成一颗真正的树之后，我们就可以在 O(logn) 的时间内求到任意区间内的答案，
    // 我们甚至可以修改序列中的值，做一些简单的维护，之后仍然可以在 O(logn) 的时间内求到任意区间内的答案，
    // 对于大规模查询的情况下，这种方法的优势便体现了出来。

    public class Status {
        public int lSum, rSum, mSum, iSum;

        public Status(int lSum, int rSum, int mSum, int iSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
            this.iSum = iSum;
        }
    }

    public int maxSubArray2(int[] nums) {
        return getInfo(nums, 0, nums.length - 1).mSum;
    }

    public Status getInfo(int[] a, int l, int r) {
        if (l == r)// 分到只剩一个数
            return new Status(a[l], a[l], a[l], a[l]);

        int m = (l + r) >> 1;
        // 分为左右区间
        Status lSub = getInfo(a, l, m);
        Status rSub = getInfo(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    // 合并
    public Status pushUp(Status l, Status r) {
        // iSum 表示 [l,r] 的区间和
        int iSum = l.iSum + r.iSum;

        // lSum 表示 [l,r] 内以 l 为左端点的最大子段和
        int lSum = Math.max(l.lSum, l.iSum + r.lSum);

        // rSum 表示 [l,r] 内以 r 为右端点的最大子段和
        int rSum = Math.max(r.rSum, r.iSum + l.rSum);

        // mSum 表示 [l,r] 内的最大子段和（左：不横跨，右：横跨）
        int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
        return new Status(lSum, rSum, mSum, iSum);
    }

    // 剑指Offer 43.1~n整数中1出现的次数（233.hot100无）
    // 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
    // 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
    // 限制：
    // 1 <= n < 2^31

    // 方法一：枚举每一数位上 1 的个数（找规律）-时间复杂度：O(logn)，空间复杂度：O(1)
    // 考虑枚举每一个数位，分别统计该数位上数字 1 出现的次数，最后将所有数位统计出的次数进行累加即可得到答案。
    public int countDigitOne(int n) {
        // mulk 表示 10^k
        // 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
        // 但为了让代码看起来更加直观，这里保留了 k
        long mulk = 1;// mulk在计算过程中会超出int范围
        long ans = 0;
        // 从个位开始，该位拥有完整循环的数量*该位1出现的次数：
        // n / (mulk * 10)) * mulk
        // 剩余不在完整的循环中的部分：
        // temp = Math.max(n % (mulk * 10) - mulk + 1, 0);
        // 剩余不在完整的循环中的部分可能在k位上没有出现1，此时式子计算结果为负，设置最小值为0
        // Math.min(temp, mulk);//不在完整的循环中的部分中的k位上最多出现mulk次1

        // e.g.求百位上，n % (mulk * 10)，1234 % 1000
        // 0 <= 234在百位上出现1的次数 <=100
        // k = 0,1,2 分别表示「个位」「十位」「百位」...
        // mulk = 10^k
        for (@SuppressWarnings("unused")
        int k = 0; n >= mulk; ++k) {
            ans += (n / (mulk * 10)) * mulk;
            long temp = Math.max(n % (mulk * 10) - mulk + 1, 0);
            ans += Math.min(temp, mulk);
            mulk *= 10;
        }

        return (int) ans;
    }

    // 方法二：动态规划（有点强行）、递归（记忆化），复杂度过高

    // 剑指Offer 46.把数字翻译成字符串
    // 给定一个数字,我们按照如下规则把它翻译为字符串：
    // 0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。
    // 请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。

    // 方法一：动态规划 + 滚动数组-时间复杂度：O(logn)，空间复杂度：O(n)
    // p q r（长度为i+1时的总翻译方法r = q（一定）+ p（可能））
    public int translateNum(int num) {
        String src = String.valueOf(num);
        int p = 0, q = 0, r = 1;
        for (int i = 0; i < src.length(); ++i) {
            p = q;
            q = r;
            r = 0;
            r += q;// 必定能取一个数字翻译得到
            if (i == 0) // 长度为1时
                continue;

            String pre = src.substring(i - 1, i + 1);// [i-1, i+1)
            if (pre.compareTo("25") <= 0 && pre.compareTo("10") >= 0) // 检查是否能取两个数字翻译
                r += p;// 取两个数字翻译得到

        }
        return r;
    }

    // 方法一：（自己写的）dp + 滚动数组-时间复杂度：O(logn)，空间复杂度：O(n)
    public int translateNum11(int num) {
        int dp0 = 1;
        int dp1 = 1;
        String numString = String.valueOf(num);
        for (int i = 1; i < numString.length(); i++) {
            int temp = dp1;
            String length2String = numString.substring(i - 1, i + 1);
            int length2Num = Integer.parseInt(length2String);
            if (10 <= length2Num && length2Num <= 25)
                temp += dp0;

            dp0 = dp1;
            dp1 = temp;
        }
        return dp1;
    }

    // 方法二：dfs bfs 题目只求多少种，而非求具体组合方式，因此没必要

    // 剑指Offer 47.礼物的最大价值
    // 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于
    // 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。
    // 给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

    // 方法一：动态规划，时间复杂度：O(mn)，空间复杂度：O(1)
    public int maxValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        for (int row = 1; row < m; row++)
            grid[row][0] += grid[row - 1][0];

        for (int column = 1; column < n; column++)
            grid[0][column] += grid[0][column - 1];

        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);

        return grid[m - 1][n - 1];
    }

    // 剑指Offer 49.丑数（264.hot100无）
    // 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
    // 说明:
    // 1 是丑数。
    // n 不超过1690。
    // 不能直接从1开始判断是不是丑数，这样复杂度不与n挂钩，e.g. 第1352个丑数是402653184

    // 方法一：最小堆（优先队列）（解决第n个 前n个的范式）-时间复杂度：O(nlogn)，空间复杂度：O(n)
    // 要得到从小到大的第 n 个丑数，可以使用最小堆实现。
    // 初始时堆为空。首先将最小的丑数 1 加入堆。
    // 每次取出堆顶元素 x，则 x 是堆中最小的丑数，由于 2x, 3x, 5x 也是丑数，因此将 2x, 3x, 5x 加入堆。
    // 上述做法会导致堆中出现重复元素的情况。为了避免重复元素，可以使用哈希集合去重，避免相同元素多次加入堆。
    // 在排除重复元素的情况下，第 n 次从最小堆中取出的元素即为第 n 个丑数。
    public int nthUglyNumber(int n) {
        int[] factors = { 2, 3, 5 };
        Set<Long> seen = new HashSet<Long>();// 计算过程中可能会越界
        PriorityQueue<Long> heap = new PriorityQueue<Long>();// 最小堆
        seen.add(1L);// 最小丑数
        heap.offer(1L);
        int ugly = 0;
        for (int i = 0; i < n; i++) {
            long curr = heap.poll();// 出队
            ugly = (int) curr;
            for (int factor : factors) {// 根据出队元素，依次计算得到3个丑数
                long next = curr * factor;
                if (seen.add(next)) // 哈希表中没有，返回true
                    heap.offer(next);// 入队
            }
        }
        return ugly;
    }

    // 方法二：动态规划（dp数组只存储丑数，只遍历丑数）-时间复杂度：O(n)，空间复杂度：O(n)
    // 方法一使用最小堆，会预先存储较多的丑数，导致空间复杂度较高，维护最小堆的过程也导致时间复杂度较高。
    // 可以使用动态规划的方法进行优化。
    // 定义数组 dp，其中 dp[i] 表示第 i 个丑数，第 n 个丑数即为 dp[n]。
    // 定义三个指针 p2, p3, p5，表示下一个丑数是当前指针指向的丑数（底倍）乘以对应的质因数（2, 3, 5）。
    // （指针指向的某个丑数*2、3、5得到下一个丑数，其中最小的数即为下一个丑数）
    // 初始时，三个指针的值都是 1
    public int nthUglyNumber2(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;// 最小丑数
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
            int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
            dp[i] = Math.min(Math.min(num2, num3), num5);

            // 每个丑数x都能派生出三个丑数2x 3x 5x
            // 可能存在一个丑数由多个丑数派生出来
            // e.g. 6可以由不同丑数 *2 *3派生出来，此时p2 p3都++，此时num2 = num3，相当于选择派生出的丑数中最小的，且把派生底倍增加
            if (dp[i] == num2)
                p2++;
            if (dp[i] == num3)
                p3++;
            if (dp[i] == num5)
                p5++;
        }
        return dp[n];
    }

    // 剑指Offer 60.n个骰子的点数
    // 把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
    // 你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

    // 方法一：动态规划-时间复杂度 O(n^2)，空间复杂度 O(n)
    // 逆向递推：f(n) = ...f(n-1) 存在数组越界问题
    // 正向递推：f(n-1) = ...f(n) 解决越界问题
    // e.g. dp[0]对temp[0]-temp[5]等额贡献，下标0表示第一种情况
    public double[] dicesProbability(int n) {
        double[] dp = new double[6];// 初始情况：1个骰子时
        Arrays.fill(dp, 1.0 / 6.0);
        for (int i = 2; i <= n; i++) {// 直到计算出第n个骰子
            double[] tmp = new double[5 * i + 1];// i个骰子时
            for (int j = 0; j < dp.length; j++)
                for (int k = 0; k < 6; k++) // 常数级
                    tmp[j + k] += dp[j] / 6.0;// 一定不会越界

            dp = tmp;
        }
        return dp;
    }

    // 剑指Offer 63.股票的最大利润（121.力扣有）
    // 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

    // 方法一：暴力法-时间复杂度：O(n^2)，空间复杂度：O(1)
    // 方法二：一次遍历-时间复杂度：O(n)，空间复杂度：O(1)
    public int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int price : prices) {
            min = Math.min(min, price);
            maxProfit = Math.max(maxProfit, price - min);
        }
        return maxProfit;
    }

}

class Test {

}

public class JianzhiOffer {
    public static void main(String[] args) {
        // Test t = new Test();

    }

}
